知识框架

ACWing

No.1 暑假每日一题：

3652.最大连续子序列

//超时版本：
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {while (cin>>k){int num[k+1]={0};int sum[k+1]={0};for(int i=1;i<=k;i++){cin>>num[i];sum[i]=sum[i-1]+num[i];}int l,r;int res=0;int resl,resr;//定左指针for( l =1;l<=k;l++){for( r=l;r<=k;r++){if(sum[r]-sum[l-1]>res){res=sum[r]-sum[l-1];resl=l;resr=r;}}}if(res==0)cout<<"0 0 0"<<endl;else      cout<<res<<" "<<resl-1<<" "<<resr-1<<endl;}return 0;
}//动态规划版本：
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;int a[N];int main()
{int n;while (cin >> n){   int f[N];  //f[i]:表示以i结尾的最大子序列和for (int i = 1 ; i <= n ; i ++ )cin >> a[i];//res：最大和，因为有可能是0，所以一开始初始化-1//l:左端点//r:右端点//tmep: 标记int res = -1, l = 0, r = 0, temp = 0;for (int i = 1 ; i <= n ; i ++ ){   //当前i的最大值，可以有前面i - 1的最大值f[i - 1] + a[i] 跟  当前a[i]比较f[i] = max(f[i - 1] + a[i], a[i]); //如果前面i - 1个数的最大子序和为0，则前面的数都是负数，都不用取，用temp标记下标if (f[i - 1] < 0) temp = i - 1; //每次更新一下最大值，如果当前以i结尾的最大子序和 > res//更新答案 ，左端点l = temp(标记的点)，因为前面的值已经不能取了，左端点就是temp//右端点是当前的结尾的数的下标if (f[i] > res) res = f[i], l = temp, r = i - 1;}//如果答案是负数，说明最大的子序和都是负数，直接输出000if (res < 0) printf("0 0 0\\n");else printf("%d %d %d\\n",res, l , r);  //反之输出最大和 ，左端点下标， 右端点下标}
}

3432. 二叉树

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int h[N];
//找某个数所在的位置
int position(int x){for(int i=1;i<=n;i++){if(h[i]==x)return i;}return 0;
}
int main() {//尝试来个 heap,没有交换环节  然后进行找位置等等cin>>x>>y;n=x;x=max(x,y);y=min(y,n);n=x;for(int i=1;i<=n;i++){h[i]=i;}int px=position(x);int py=position(y);vector<int>ans;while(x!=1){ans.push_back(x);x=h[position(x)/2];}ans.push_back(1);while(y>=1){for(auto i:ans){if(i==y){cout<<i<<endl;return 0;}}y=h[position(y)/2];}return 0;
}//因为是满二叉树, 加上二叉树的一些性质: [子节点的数 / 2]向下取整就可以得到父节点，所以我们只需要每次判断x跟y哪个大，然后谁大就说明谁的层数比较深 或者 同层，所以我们只需要每一次看谁大就除2,看什么时候两个数相等，就说明那个点是重合点，最后直接输出x或者y都行#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;
int x, y;int main()
{cin >> x >> y;while (true){if (x > y) x /= 2;else if (y > x) y /= 2;else break;}cout << x << endl;return 0;
}

3559”围圈报数

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;for(int j=0;j<n;j++){cin>>m;vector<int>ans;k=0;//标志到3int vis[m+1]={0};for(int i=1;ans.size()!=m;i++ ){if(vis[i]==1){//如果已经在了 就跳过；if(i==m)i=0;continue;}k=(k+1)%3;if(k==0){ans.push_back(i);vis[i]=1;}if(i==m)i=0;}for(int i=0;i<ans.size();i++){if(i==0)cout<<ans[i];else cout<<" "<<ans[i];}cout<<endl;}return 0;
}

4520质数

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int iszhi(int x){if(x<2)return 0;for(int i=2;i<=sqrt(x);i++){if(x%i==0)return 0;}return 1;
}
int main() {cin>>n;// cout<<to_string(n).size()<<endl;while (n--){cin>>m;//加的数字 自家， 然后统计长度，然后进行原数字x*百千万， 然后计算；for(int i=1; ; i++){x=m*pow(10,to_string(i).size())+i;if(iszhi(x)==1){cout<<x<<endl;break;}}}return 0;
}

3601：成绩排序

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,k,g,d;
long long x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{float num;string name;int  age;}stu[N];bool cmp(node a,node b){if(a.num!=b.num){return a.num<b.num;}else if(a.name!=b.name){return a.name<b.name;}else{return a.age<b.age;}
}
int main() {cin>>n;for(int i=0;i<n;i++){cin>>stu[i].name>>stu[i].age>>stu[i].num;}sort(stu,stu+n,cmp);for(int i=0;i<n;i++){cout<<stu[i].name<<" "<<stu[i].age<<" "<<stu[i].num<<endl;}return 0;
}

2074：倒计数

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;for(int i=1;i<=n;i++){cin>>x>>k;int co=0;vector<int>ans;for(int j=0;j<x;j++){cin>>y;ans.push_back(y);}for(int j=0;j<x;j++){if(ans[j]==k){vector<int>ans1;vector<int>ans2;for(int z=k;z>=1;z--){ans1.push_back(z);}for(int z=j;ans2.size()<k&&z<x;z++){ans2.push_back(ans[z]);}if(ans1==ans2){co++;}}}cout<<"Case #"<<i<<": "<<co<<endl;}return 0;
}

4268：性感素数

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int isZ(int x){if(x<2)return 0;for(int i=2;i<=x/i;i++){if(x%i==0)return 0;}return 1;
}int main() {cin>>n;if(isZ(n)==1&&(isZ(n-6)||isZ(n+6))){cout<<"Yes"<<endl;if(isZ(n-6))cout<<n-6<<endl;else cout<<n+6<<endl;}else{cout<<"No"<<endl;for(int i=n+1; ;i++){if(isZ(i)&&(isZ(i-6)||isZ(i+6))){cout<<i<<endl;break;}}}return 0;
}

4269：校庆

//对于N要进行适应性的更改，对于字段错误
//使用无序的去重的set；；： unordered_set   以及函数count
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
//无序的去重的set
unordered_set<string>a,b,c;int main() {cin>>n;for(int i=0;i<n;i++){cin>>str;a.insert(str);}cin>>m;while(m--){cin>>str;b.insert(str);}int count=0;for(auto p:b){count=count+a.count(p);}cout<<count<<endl;string ri="99999999";if(count==0){c=b;}else{c=a;}for(auto p:c){if(b.count(p)==0)continue;string birth=p.substr(6,8);if(birth<ri)ri=birth,str=p;}cout<<str<<endl;return 0;
}

4273：链表合并

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
//无序的去重的set
unordered_set<string>a,b,c;
struct node
{int data;int next;int id;
}ss[N];int main() {int h1,h2;cin>>h1>>h2;cin>>n;while(n--){cin>>x;ss[x].id=x;cin>>ss[x].data>>ss[x].next;}vector<int>a,b,res;for(int i=h1;i!=-1;i=ss[i].next){a.push_back(i);}for(int i=h2;i!=-1;i=ss[i].next){b.push_back(i);}if(a.size()<b.size())swap(a,b);reverse(b.begin(),b.end());for(int i=0,j=0; i<a.size() ;i++){res.push_back(a[i]);if((i+1)%2==0&&j<b.size())res.push_back(b[j++]);}for (int i = 0; i < res.size(); i ++ ){printf("%05d %d ", res[i], ss[res[i]]);if (i == res.size() - 1) printf("-1\\n");else printf("%05d\\n", res[i + 1]);}return 0;
}

4275：dijkstra序列

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int mp[1005][1005];
int vis[N]={0};
int dist[N];
int p[N];
int dij(int index){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)dist[i]=mp[index][i];dist[index]=0;vis[index]=1;for(int i=1;i<=n;i++){int t=p[i];vis[t]=1;for(int j=1;j<=n;j++){if(vis[j]==0&&dist[j]<dist[t]){return 0;}}for(int j=1;j<=n;j++){if(dist[j]>dist[t]+mp[t][j]){dist[j]=dist[t]+mp[t][j];}}}
}
int main() {cin>>n>>m;memset(mp,inf,sizeof(mp));while(m--){cin>>x>>y>>z;mp[x][y]=mp[y][x]=z;}cin>>m;while(m--){for(int i=1;i<=n;i++)cin>>p[i];if(dij(p[1]))cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

692：G巴士计数

	//对于N要进行适应性的更改，对于字段错误#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define N 100100int n,m,k,g,d;int x,y,z;char ch;string str;int main() {cin>>n;for(int i=1;i<=n;i++){cin>>m;vector<int>v[N];for(int j=1;j<=m;j++){cin>>x>>y;v[j].push_back(x);v[j].push_back(y);}cin>>d;cout<<"Case #"<<i<<":";for(int j=1;j<=d;j++){int res=0;cin>>x;for(int q=1;q<=m;q++){if(x<=v[q][1]&&x>=v[q][0]){res++;}}cout<<" "<<res;}cout<<endl;}return 0;}

4461：范围分区

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 5010;
int n, x, y;
int ans[N]; int main()
{int T;cin >> T;for (int t = 1; t <= T; t ++){cin >> n >> x >> y;int sum = 0; //算出总和 1 - nfor (int i = 1; i <= n; i ++) sum += i;//x , y是一个比例，所以1 -> n的总和加起来除x+y是可以完全除尽的//因为如果x跟y的比例不能够让1-n个数的总和除尽(即取模为0)，//那就不能够取到[x,y]这种比例的结果if (sum % (x + y)) printf("Case #%d: IMPOSSIBLE\\n", t);  //不能除尽，就直接输出impossibleelse {//这个就是总和除 (x + y)的比例，然后b表示的是比例每一份有多少int b = sum / (x + y);   memset(ans, 0, sizeof ans);  //记录选取的每一个数，多组数据，每一次清零printf("Case #%d: POSSIBLE\\n", t);  //成功输出int cnt = 0;    //艾伦选取的个数int s = x * b;   //x是艾伦的比例， 比例 乘以 每份比例的数量就是艾伦选取的数的总数//然后从后往前选n -> 1，因为如果从头选，你就有可能选不到//比如样例n=8,x=3,y=6;//1-8总和是36, 每一份比例是b = 8/(3+6) = 4//x比例是3，每一份b是4，所以艾伦选的数的总和是3*4=12，//然后从1-n中选取能够加起来是12的数，12345678，这样看来加完前面1+2+3+4=10 不够12//这样就不能够成功取到//如果从后面往前87654321，可以取到8+4就可以直接取到了for (int i = n; i >= 1; i --)   {if (s >= i) //s表示艾伦取的总数，然后每一次取小于s的数{ans[cnt ++] = i; s -= i;    //然后取到一个数记录下来，然后累减这个数}}cout << cnt << endl; // 输出个数for (int i = 0; i < cnt; i ++)  //输出记录下来的每个数cout << ans[i] << ' ';cout << endl;}}
}

3307：破纪录者

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;int res=0;int maxx=0;for(int i=1;i<=n;i++){cin>>x;res=0;maxx=0;int a[x+1];for(int j=1;j<=x;j++){cin>>a[j];}for(int j=1;j<=x;j++){if(j==1){maxx=max(maxx,a[j]);if(a[j]>a[j+1]){res++;}}else if(j==x){if(a[j]>maxx)res++;}else{if(a[j]>maxx&&a[j]>a[j+1]){res++;}maxx=max(a[j],maxx);}}cout<<"Case #"<<i<<": "<<res<<endl;}return 0;
}

3391“今年的第几天？

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,k,g,d,t;
int x,y,z;
char ch;
string str;
vector<int>v[N];int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int sumday(int y,int m,int d){int res=0;for(int i=0;i<m;i++){res=res+day[i];}res=res+d;if((y%4==0&&y%100!=0)||(y%400==0)){if(m>2)res++;}return res;
}
int main() {int y,m,d;while(cin>>y>>m>>d){cout<<sumday(y,m,d)<<endl;}return 0;
}

3593：单词统计

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
typedef long long LL;
typedef pair<LL,LL>PLL;
long long n,m,k,g,d,t;
int x,y,z;
char ch;
string str;
vector<int>v[N];
priority_queue<LL,vector<LL>>q1;
priority_queue<PLL,vector<PLL>>q2;
priority_queue<int,vector<int>>q;
PLL p[N];
int main() {vector<int>ans;while(cin>>str){if(str.back()=='.'){ans.push_back(str.size()-1);break;}else{ans.push_back(str.size());}}for(auto p:ans){cout<<p<<" ";}return 0;
}

3452：进制转化

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
typedef long long LL;
typedef pair<LL,LL>PLL;
long long n,m,k,g,d,t;
int x,y,z;
char ch;
string str;
vector<int>v[N];
priority_queue<LL,vector<LL>>q1;
priority_queue<PLL,vector<PLL>>q2;
priority_queue<int,vector<int>>q;
PLL p[N];
string str1;
int main() {while (cin>>str1){if(str1[0]=='-'){str=str1.substr(3,str1.size()-3);}else{str=str1.substr(2,str1.size()-2);}reverse(str.begin(),str.end());int res=0;for(int i=str.size()-1;i>=0;i--){int num=0;if(str[i]<='9'){num=(str[i]-'0')*pow(16,i);}else if(str[i]=='A'||str[i]=='a'){num=10*pow(16,i);}else if(str[i]=='B'||str[i]=='b'){num=11*pow(16,i);}else if(str[i]=='C'||str[i]=='c'){num=12*pow(16,i);}else if(str[i]=='D'||str[i]=='d'){num=13*pow(16,i);}else if(str[i]=='E'||str[i]=='e'){num=14*pow(16,i);}else if(str[i]=='F'||str[i]=='f'){num=15*pow(16,i);}res=res+num;}if(str1[0]=='-')cout<<"-"<<res<<endl;else cout<<res<<endl;}return 0;
}

3596：a+b

(竖式法)
我们可以输入两个字符串
再开两个数组来储存每个数
每一位上的数。
不过a0a0存放的是最后一个数
这样就能够实现数字末尾对齐
然后每位对齐实现竖式计算！

#include <bits/stdc++.h>
using namespace std;int a[1005], b[1005], cnt;
string x, y;
int main() {while (cin >> x >> y) {memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));for (int i = 0; i < x.size(); i++)a[x.size() - 1 - i] = x[i] - '0';for (int i = 0; i < y.size(); i++)b[y.size() - 1 - i] = y[i] - '0';cnt = max(x.size(), y.size());for (int i = 0; i < cnt; i++) {a[i] += b[i];a[i + 1] += a[i] / 10;a[i] %= 10;}while (a[cnt])cnt++;for (int i = cnt - 1; i >= 0; i--)cout << a[i];cout << endl;}return 0;
}

3667：切木棍

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {while(cin>>n){if(n%2!=0){cout<<0<<endl;continue;}n=n/2;cout<<(n-1)/2<<endl;}return 0;
}

3712.根能抵达的点

// 对于 小于val  的不进行搜素哦，  不用删除。。#include <bits/stdc++.h>
using namespace std;const int N = 4e5 + 5;
int t, n, y;int en, first[N];
struct edge {int e, d, next;
}ed[N];void add_edge(int s, int e, int d) {en++;ed[en].e = e, ed[en].d = d;ed[en].next = first[s];first[s] = en;
}int ans;
void dfs(int x, int val) {ans++;for (int p = first[x]; p; p = ed[p].next) {if (ed[p].d >= val) dfs(ed[p].e, val); //  只有当前的边权大于等于val值才可以dfs，因为小于val值的边已经删掉了}
}bool check(int x) {ans = 0;dfs(0, x);if (ans <= y) return 1;  // 1表示满足else return 0; // 0表示不满足
}int main() {cin >> t;while (t--) {en = 0;memset(first, 0, sizeof first);cin >> n >> y;for (int i = 1; i <= n - 1; i++) {int u, v, w;cin >> u >> v >> w;add_edge(u, v, w);  // 存图}int l = 0, r = 1e7;  // 注意，二分边界必须要1e7!!while (l < r) {  // 二分int mid = l + r >> 1;if (check(mid)) r = mid;  // 满足条件else l = mid + 1;   // 不满足}cout << l << endl;}
}

3589：平方因子

#include <bits/stdc++.h>
using namespace std;int main() {int n;int flag=0;while(cin>>n){flag=0;for(int i=2;i*i<=n ;i++){if(n%(i*i)==0){flag=1;break;}}if(flag==1)cout<<"Yes"<<endl;else cout<<"No"<<endl;}
}

3449：数字根

//当数据量变得比较大的时候，就考虑使用字符串进行处理。to_string()
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;string s;int main()
{while (cin >> s, s != "0") //如果是0的话就直接跳过{int res = 0; //数字根。while (res == 0 || res > 9)  //如果是第一个，或者是当前的数字根不是一位{   res = 0;   //每次初始化数字跟for (char t : s)  //那么累加当前数的每一位数res += t - '0';if (res > 9) s = to_string(res); //如果当前的数字根不是一位数，将res转成字符串赋值给s}cout << res << endl; //最后输出数字根}return 0;
}

3526：素数

#include <bits/stdc++.h>
using namespace std;int issu(int x){if(x<2)return 0;for(int i=2;i*i<=x;i++){if(x%i==0)return 0;}return 1;
}int main() {int n;while(cin>>n){vector<int>ans;for(int i=1;i*10+1<n;i++){if(issu(i*10+1)==1)ans.push_back(i*10+1);}if(ans.size()==0){cout<<-1;}else{for(auto p:ans)cout<<p<<" ";}cout<<endl;}
}

2070：自行车之旅

#include <bits/stdc++.h>
using namespace std;int main() {int n,x;cin>>n;for(int j=1;j<=n;j++){cin>>x;int arr[x+1];for(int i=0;i<x;i++)cin>>arr[i];int res=0;for(int i=0;i<x;i++){if(i!=0 && i!=x-1){if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])res++;}}cout<<"Case #"<<j<<": "<<res<<endl;}
}

No.2 背包问题

0-1背包问题：

二维：01背包问题::「0-1 背包」即是不断对第 i 个物品的做出决策，「0-1」正好代表不选与选两种决定。

思路：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pkYuzWzk-1679671509855)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220221213629976.png)]

#include<bits/stdc++.h>using namespace std;const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 int main() 
{int n, m;   cin >> n >> m;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];//制作一个二维表格for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){//  当前背包容量装不进第i个物品，则价值等于前i-1个物品if(j < v[i]) f[i][j] = f[i - 1][j];// 能装，需进行决策是否选择第i个物品else    f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);}           cout << f[n][m] << endl;return 0;
}

一维进化：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Klbxj5H9-1679671509856)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220221214906859.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HebQYdnE-1679671509857)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220221215043828.png)]

for(int i = 1; i <= n; i++) for(int j = m; j >= 0; j--){if(j < v[i]) f[i][j] = f[i - 1][j];  // 优化前f[j] = f[j];            // 优化后，该行自动成立，可省略。else    f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  // 优化前f[j] = max(f[j], f[j - v[i]] + w[i]);                   // 优化后}    //实际上，只有当枚举的背包容量 >= v[i] 时才会更新状态，因此我们可以修改循环终止条件进一步优化for(int i = 1; i <= n; i++)
{for(int j = m; j >= v[i]; j--)  f[j] = max(f[j], f[j - v[i]] + w[i]);
}

版本三：我们注意到在处理数据时，我们是一个物品一个物品，一个一个体积的枚举。

因此我们可以不必开两个数组记录体积和价值，而是边输入边处理。

#include<bits/stdc++.h>using namespace std;const int MAXN = 1005;
int f[MAXN];  // int main() 
{int n, m;   cin >> n >> m;for(int i = 1; i <= n; i++) {int v, w;cin >> v >> w;      // 边输入边处理for(int j = m; j >= v; j--)f[j] = max(f[j], f[j - v] + w);}cout << f[m] << endl;return 0;
}

完全背包问题：

题目：物品数量无限制

#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i = 1 ; i <= n ;i ++){cin>>v[i]>>w[i];}for(int i = 1 ; i<=n ;i++){for(int j = 0 ; j<=m ;j++){for(int k = 0 ; k*v[i]<=j ; k++)f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}}cout<<f[n][m]<<endl;
}

多重背包问题I：

物品数量有固定的限制S[]

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e2+10;
int  f[N][N],w[N],v[N],s[N];
int main()
{int n,V;cin>>n>>V;for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];for(int i=1;i<=n;i++){for(int j=0;j<=V;j++){for(int k=0;k<=s[i];k++){if(k*v[i]<=j) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}}}cout<<f[n][V];return 0;
}

No.3 周赛:

第 53 场周赛

4425.改变数字

//数字认为字符串输入；；；防止爆int
#include<bits/stdc++.h>
using namespace std;
#define N 10001int main()
{string x;cin>>x;vector<int>ans;vector<int>ans2;for(auto s:x){int num=s-'0';ans.push_back(num);}for(int i=0;i<ans.size();i++){int num=ans[i];if(i==0){if((9-num)>0&&(9-num)<num){ans2.push_back(9-num);}else{ans2.push_back(num);}}else{if((9-num)>=0&&(9-num)<num){ans2.push_back(9-num);}else{ans2.push_back(num);}}}for(auto i:ans2){cout<<i;}
return 0;
}

4426.整除字串

//字串比连续，子序列不一定连续；
//被4整除，即数字的最后两位能够被四整除；因为：nab=n*100+ab；
#include<bits/stdc++.h>
using namespace std;
#define N 10001int main()
{string s;cin>>s;long long count=0;for(int i=0;i<s.size();i++){//一位的if((s[i]-'0')%4==0)count++;//两位的if((i!=0)&&((s[i-1]-'0')*10+(s[i]-'0'))%4==0){count=count+i;// 因为前面有i位数}}cout<<count<<endl;return 0;
}

第56场周赛

4483.格斗场：双指针标记

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

第一种方法：双指针
//在本题中因为如果i在后面限制条件下直到找到j为对手才满足条件；那么i+1选手想要找到满足条件的位置最少为i+1 ； 即第二个指针
// 不用再从1开始了；用第二个指针进行标记；
第二种方法：low_bouner;那类的直接找到//对于每一个i，维护一个j，使得a[j] - a[i] 是大于 k //的第一个数。则前一个数可以删掉下面这个是超时的：就是因为输出超时了
#include <bits/stdc++.h>
using namespace std;
#define  N 100100
int n,m,s,k,d;
int x,y,z;
vector<int>v[N];
int vis[N]={0};
int main()
{cin>>n>>k;int a[n+1];int vis[N]={0};int j=1;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);for(int i=0;i<n;i++){while(j<n&&a[j]-a[i]<=k)j++;if(a[j-1]>a[i])vis[a[i]]=1;}int coun=0;for(int i=0;i<n;i++){if(vis[a[i]]==0)coun++;}cout<<coun<<endl;return 0;
}下面这个是没有超时的
#include <bits/stdc++.h>
using namespace std;
#define  N 100100
int n,m,s,k,d;
int x,y,z;
vector<int>v[N];
int vis[N]={0};
int main()
{cin>>n>>k;int a[n+1];int vis[N]={0};int j=1;for(int i=0;i<n;i++){cin>>a[i];}int coun=n;sort(a,a+n);for(int i=0;i<n;i++){while(j<n&&a[j]-a[i]<=k)j++;if(a[j-1]>a[i])coun--;}cout<<coun<<endl;return 0;
}

双指针讲解：

双指针法充分使用了数组有序这一特征，

对撞指针是指在数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。对撞数组适用于连续数组和字符串，也就是说当你遇到题目给定连续数组和字符床时，应该第一时间想到用对撞指针解题。力扣209. 长度最小的子数组给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tCIc9Bhs-1679671509857)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220626210507366.png)]

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;int start = 0, end = 0;int sum = 0;while (end < n) {sum += nums[end];while (sum >= s) {ans = min(ans, end - start + 1);sum -= nums[start];start++;}end++;}return ans == INT_MAX ? 0 : ans;}
};

4484.有限小数

问题：1：小数转其它进制问题

​ 2：判断位数是否有限问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rtvsybvc-1679671509857)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220625152151810.png)]

首先先化简即先求p与q 的最大公约；然后因为主要是看小数部分；即直接化为最简分子分母；也就是小数部分；；然后乘以进制b；；一直乘以看是否为整数；；所以 分子/分母*b^k   所以就是看必须用最大公因数去约分；；比如b=21   好多不能用除以21   但是21=3*7  可以约分；
#include<iostream>
#include<cstring>
using namespace std;
#define int long long
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}
signed main()
{int t; scanf("%lld", &t);while(t --){int p, q, b; scanf("%lld %lld %lld", &p, &q, &b);int d = gcd(p, q);q /= d;while(q > 1){int d = gcd(q, b);if(d == 1) break;while(q % d == 0) q /= d;}if(q > 1) puts("NO");else puts("YES");}
}

第57场周赛

4486.数字操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2m8Dolfs-1679671509858)(https://cdn.acwing.com/media/article/image/2022/06/25/157380_1239eee2f4-Pic2.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QUbrnxEV-1679671509858)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220626202644068.png)]

第一种常规解法（错误的）：先看看是否可以进行开根号，如果可以直接开根号，如果不可以就先乘以再开根号等；但是没有那种先、、、

#include <bits/stdc++.h>
using namespace std;
#define  N 100100
int n,m,s,k,d;
int x,y,z;
vector<int>v[N];
int vis[N]={0};
int main()
{cin>>n;int flag=0;int count=0;while(n>1){int t=sqrt(n);if(t*t==n){count++;n=t;}else{for(int q=t; q<n;q++){if(q*q%n==0){n=q;count=count+2;break;}if(q==n-1)flag=1;}}if(flag==1)break;}cout<<n<<" "<<count<<endl;return 0;
}

第二种：将一个数字进行质因子分解；；开一次方就是将各个质因子的指数➗2；所以第一步是要将各个的指数变为2的指数，因为不要求求要乘以的数字x，即如果输入的数字是目标形式直接连续开，如果不是，那就成个x， [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0VX3mU3q-1679671509858)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220626203255392.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8jpLl1xb-1679671509859)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220626203355112.png)]

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;const int MaxV=1E6+10;int num,step;
int d[MaxV];                        //d[i]记录质因数i的指数int Init()                          //先分解质因数
{int t=num,maxn=sqrt(t),maxc=-1;for(int i=2;i<=maxn;i++){while(t%i==0){t/=i;d[i]++;maxc=max(maxc,d[i]);}}//最后一个质因子；；if(t>1){d[t]++;maxc=max(maxc,d[t]);}return maxc;                    //取所有因数的最大值
}int main()
{int maxc;long long t=1;                  //记录所有质因数的乘积(不包括幂)cin>>num;maxc=Init();int i=0,sum2=0;while(maxc>pow(2,i))i++;        //寻找最小的2^n>=maxcint l=i;                        //记录结果for(int i=1;i<=num;i++){if(d[i]){t*=i;                   //记录所有质因数的乘积sum2+=pow(2,l)-d[i];    //对(不用乘)的数字的特殊处理,即直接开根号}}if(sum2==0||i==0)               //特殊情况,直接开根号{cout<<t<<" "<<i<<endl;}else{cout<<t<<" "<<i+1<<endl;    //正常情况,先乘一次,再开根号}return 0;
}

4487. 最长连续子序列：前缀和+单调栈

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N6fltfDC-1679671509859)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220626204547945.png)]

所以第一个开始的元素必须大于100；这个很像那个前连续和的问题；

首先是前缀和问题：

好像一般都是先列出不等式，然后变化；；

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0iCyW9GP-1679671509859)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220628234429547.png)]

// 所以可以转化成   几个数字相加为>0  即可；
//  定尾巴，动前面的// 将前面的逆的序列删掉； 最后称为一个单调递减的数列；

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KMCMrLv4-1679671509859)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220629002046383.png)]

单调栈维护一个单调递减序列
如果小于，直接入栈
如果大于，说明前面能找到答案，二分找最前面的

top表示栈顶元素的位置；；
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int a[N],n,ans;
int s[N],top;signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i]+=a[i-1]-100;}s[++top]=0;for(int i=1;i<=n;i++){if(a[i]==a[s[top]])continue;if(a[i]<a[s[top]])s[++top]=i;else{int l=1,r=top;while(l<r){int mid=l+r>>1;if(a[i]>a[s[mid]])r=mid;else l=mid+1;}ans=max(ans,i-s[r]);}}cout<<ans;
}

第 59 场周赛

4491：数组操作

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,t,k,d;
int x,y,z;
char ch;
string s;
vector<int>v[N];
int main()
{cin>>n;int ans=0;int miarr=0;for(int i=0;i<n;i++){cin>>x;ans+=x;miarr=min(miarr,ans);}cout<<ans-miarr<<endl;return 0;
}

4492：减法操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hZ8ZbCXC-1679671509860)(C:\\Users\\86177\\AppData\\Roaming\\Typora\\typora-user-images\\image-20220710214654436.png)]

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z;
char ch;
string s;
vector<int>v[N];
int main()
{cin>>n;if(n%2==0){cout<<n/2<<endl;}else{for(k=3;k*k<=n;k=k+2){if(n%k==0){n=n-k;break;}}if(n%2==0)cout<<n/2+1;else cout<<"1";}return 0;
}

4493.环形连通分量

难点：怎么判断一个图中的部分连通分量是环形的：

第61场周赛

4497：分糖果：

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,k,g,d;
long long x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;while(n--){cin>>x>>y>>z;x=(x+y+z)/2;cout<<x<<endl;}return 0;
}

第62场周赛：

4500：三个元素

成立这个等式
我们可以先排序一遍
然后最左边那个数可以选最小值
最右边那个数可以选最大值
中间那个数模拟一下
如果那个数和那两个数构成等式
那么直接输出即可
如果没有等式成立
输出三个-1#include<bits/stdc++.h>
using namespace std;
int n;
struct o{int x,y;
}a[3005];
bool f(o x,o y){return x.x<y.x;//按照大小排序
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i].x,a[i].y=i;//这里还需要用一个数记录下标sort(a+1,a+1+n,f);//排序int x=a[1].x,y=a[n].x;for(int i=2;i<n;i++)if(x<a[i].x&&a[i].x<y){//如果等式成立cout<<a[1].y<<' '<<a[i].y<<' '<<a[n].y;//输出他们的下标return 0;}cout<<"-1 -1 -1";//如果没有等式成立 输出三个-1
}

4501：收集卡牌

//自己的 潮湿的//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,k,g,d,t;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n>>m;map<int,int>mp;for(int i=1;i<=n;i++)mp[i]=0;while(m--){cin>>x;mp[x]++;int flag=0;for(int i=1;i<=n;i++){if(mp[i]<=0){flag=1;break;}}if(flag==1){cout<<0;}else{cout<<1;for(int i=1;i<=n;i++)mp[i]--;}}return 0;
}、、未超时的用 bb 数组统计卡牌个数，一旦出现前面没有出现的卡牌，计数器 cnt++cnt++，只要 cnt==ncnt==n，就代表着一次卡片集全，输出 11，且将 bb 的每个数组元素减一，若减去后的数组元素等于 00，cnt–cnt–，否则输出 00。（这有两个减号，但不知道为啥被吞了）  #include <bits/stdc++.h>
using namespace std;
int a, b[100010];int main () {int n, m, cnt = 0;cin >> n >> m;for (int i = 1; i <= m; i++){cin >> a;b[a] ++;if (b[a] == 1) cnt ++;//若 a 只出现了这一次，就多了一个从前没出现的数if (cnt == n){//所有数都出现过cout << 1;for (int j = 1; j <= n; j++){b[j] --;if (b[j] == 0) cnt --;//如果这个数用掉了，这个数 j 等于没有出现}}else cout << 0;}return 0;
}

第 64 场周赛：

1. A + B

#include<bits/stdc++.h>
using namespace std;
int main(){int a,b;cin>>a>>b;cout<<a+b<<endl;return 0;
}

4506. 三国语言

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;while(n--){cin>>str;int size=str.size();if(str.substr(size-2,2)=="po"){cout<<"FILIPINO"<<endl;}else if(str.substr(size-4,4)=="desu"||str.substr(size-4,4)=="masu"){cout<<"JAPANESE"<<endl;}else{cout<<"KOREAN"<<endl;}}return 0;
}

4507.子数组异或和

/*
异或性质:相同数异或结果为0
异或前缀和:
s[i]表示前i个字母的异或前缀和,求[i ~ j]这一段的异或和:s[j] ^ s[i - 1]
因为s[j]是a[1] ^ a[2] ^ ... ^ a[i - 1] ^ a[i] ^ ... ^ a[j]
s[i - 1]是a[1] ^ a[2] ^ ... ^ a[i - 1]
所以s[j] ^ s[i - 1] == a[i] ^ ... ^ a[j],即是[i ~ j]这一段的异或和【条件1】该连续子数组的前一半元素的异或和等于其后一半元素的异或和
说明 左半边 ^ 右半边 = 0
假设这一连续子数组的下标是[i ~ j],所以即是[i ~ j]这一段的异或和等于0
所以s[j] ^ s[i - 1] == 0,所以由第一个条件可知 ==> s[j] == s[i - 1]
所以可以枚举每一个j,找到j左边异或前缀和与s[j]相等的数目,并加入到答案中
可以使用哈希表来记录之前的异或前缀和的值出现的次数
【条件2】该连续子数组的长度为偶数
对于枚举没有一个j时,只需要将下标奇偶性与j相同的并且满足条件1的数目加到答案中即可
*/
#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 300010;int n, a[N];int main()
{scanf("%d", &n);for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);unordered_map<int, int> h[2]; //h[0]是下标为偶数的哈希表,h[1]是下标为奇数的哈希表int s = 0;  //异或前缀和ll res = 0; //记录答案h[0][s] ++;for(int i = 1; i <= n; i ++) //枚举{s ^= a[i];  //异或前缀和s[i]res += h[i % 2][s];  //将之前的异或前缀和为s的数目加入答案h[i % 2][s] ++;     //将异或前缀和为s的数目加1}cout << res << endl;return 0;
}

4508.移动的点

第67场周赛：

AcWing 4609. 火柴棍数字

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];int main() {cin>>t;// 因为 两根就多了一位；即去掉>=4的；然后就生下了 数值 1和7while(t--){cin>>n;string s="";int num=0;if(n%2==0){num=n/2;}else{num=(n-3)/2;s=s+'7';}while(num--)s=s+'1';cout<<s<<endl;}return 0;
}

AcWing 4610. 列表排序

AcWing 4611. 串联数字

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
typedef LL long long;
int n,m,k,g,d;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];
LL a[N];
map<LL,LL>mp[11];
int cnt[N];
int main() {cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];LL temp=a[i];if(temp==0)cnt[i]=1;else{while(temp){cnt[i]++;temp/=10;}}mp[cnt[i]][a[i]%k]++;}for(int i=1;i<=n;i++){for(int j=1;j<=10;j++){LL x = a[i]*pow(10,j)%k;if(mp[j].find(k-x)%k!= mp[j].end()){ans=ans+mp[j][(k-x)%k];if(cnt[i]==j && a[i]%k==(k-x)%k) ans--;}}}cout<<ans<<endl;return 0;
}

第 68 场周赛

AcWing 4612. 去掉0

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];int main() {//从第一个  1  开始int res =0;cin>>t;while(t--){x=0,y=0;res =0;cin>>str;for(int i=0;i<str.size();i++){if(str[i]=='1'){x = i;break;}}for(int j=str.size()-1;j>=0;j--){if(str[j]=='1'){y=j;break;}}if(x==y){cout<<0<<endl;continue;}for(int i=x+1;i<y&&i<str.size();i++){if(str[i]=='0'){res++;}}cout<<res<<endl;}return 0;
}

AcWing 4613. 方格跳跃

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];int main() {//小朋友需要选择任意一个方格作为自己的初始位置，并从初始位置开始，按照每个方格的指示跳跃方向进行连续跳跃。//  无限制横跳 为不能进入的区域。cin>>n;int res=0;cin>>str;int flag =0;for(int i=0;i<str.size()-1;i++){if(str[i]=='>'&&str[i+1]=='<'){flag=1;x=i;y=i+1;break;}}if(flag==0){cout<<str.size()<<endl;}else{for(int i=0;i<x&&i<str.size();i++){if(str[i]=='>'){x=i;break;}}res = res +x;for(int j =str.size()-1;j>=y&&j>=0;j--){if(str[j]=='<'){y=j;break;}}res = res+(str.size()-y-1);cout<<res<<endl;}return 0;
}

AcWing 4614. 匹配价值

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];int main() {int q;scanf("%d%d%d", &n, &m, &q);vector<int>w;for(int i=0;i<n;i++){cin>>x;w.push_back(x);}vector<string>ss;for(int i=0;i<m;i++){cin>>str;ss.push_back(str);}while(q--){cin>>str>>k;int res =0;for(auto sr:ss){int v=0;for(int i=0;i<n;i++){if(str[i]==sr[i]){v+=w[i];}}if(v<=k)res++;}cout<<res<<endl;}return 0;
}

第70场周赛：

AcWing 4618. 两个素数

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];
int isP(int x){for(int i=2;i<x;i++){if(x%i==0)return 0;}return 1;
}
int main() {cin>>x;for(int i=2;i<x;i++){if(isP(i)){if(x%i==0 &&(x/i)>=i){cout<<i<<" "<<x/i<<endl;break;}}}return 0;
}

AcWing 4619. 减法操作

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;int arr[n+1];int flag=0;for(int i=0;i<n;i++)cin>>arr[i];for(int i=0;i<n-1;i++){x = arr[i];if(x%2!=0){x--;arr[i+1]--;if(x<0 || arr[i+1]<0)flag =1;}}if(flag ==1 || arr[n-1]%2!=0)cout<<"NO"<<endl;else cout<<"YES"<<endl;return 0;
}

AcWing 4620. 旅行

这个也是复杂的图等等；；路径问题。。

第 71 场周赛：

AcWing 4621. 三个整数

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];int a,b,c,d;
int main() {cin>>a>>b>>c>>d;int flag = 0;for(int i = a;i<=b;i++){for(int j=b;j<=c;j++){x = i+j;x--;while(x){if(x<=d&&x>=c){cout<<i<<" "<<j<<" "<<x<<endl;flag =1;break;}x--;}if(flag == 1 ){break;}}if(flag == 1){break;}}return 0;
}

AcWing 4622. 整数拆分

问题解析
f(x)表示整数 x 的除本身之外的最大因数，那么当x为质数时，f(x)=1，所以这一题其实就是让我们用最少的质数相加得到x，质数的个数就是这一题的答案。

1、那么当x为质数时，f(x)直接就等于1了，不用拆分。
2、当x为偶数时，这里就要讲一个非常著名的猜想：哥德巴赫猜想。哥德巴赫猜想是说，对于任意一个大于2的偶数都可以拆分成两个质数之和（虽然只是猜想，没法验证，但是用起来是完全没问题的）。所以当x为偶数时，结果就是2。
3、当x为奇数时，我们要再分情况考虑，如果x-2是一个质数，那么我们把x拆分成x-2和2就可以得到最小的结果，结果是2；如果x-2不是质数，我们就可以把x拆分成3和一个偶数，这样的结果是3.

bool check(int x)
{for (int i = 2; i <= x / i; i++){if (x % i == 0)return false;}return true;
}
void solve()
{int n;cin>>n;if(check(n)){cout<<1;}else if(n%2==0)cout<<2;else if(check(n-2))cout<<2;else cout<<3;
}

AcWing 4623. 买糖果：

问题解析
这题看着花里胡哨，实则解法非常暴力，我们只用一轮一轮的模拟即可，用cnt记录可以买到的糖果数。

1、初始先计算如果所有的糖果都买需要多少钱，记为sum。
2、如果我们的钱t大于sum，那我们就可以通过：当前店铺数*t/sum来得到我们可以一直买下去的糖果数，之后我们的金钱变为t%sum。
3、当sum大于t时，我们遍历一遍所有的店铺，如果这个店铺的糖果我们能买，则cnt++，金钱减去这个店铺的售价a[i]。如果这个店铺的糖果我们不能买，我们用st数组记录下这个店铺，并把它从sum中减去。
4、重复第2，3操作，知道我们一个糖果都买不了为止。

int a[N];
bool st[N];
void solve()
{int n, t, sum = 0, cnt = 0;cin >> n >> t;int ans = n;for (int i = 1; i <= n; i++){cin >> a[i];sum += a[i];}while (1){cnt += ans * (t / sum);t %= sum;bool flag = false;for (int i = 1; i <= n; i++){if (st[i])continue;if (t >= a[i]){cnt++;t -= a[i];flag = true;}else{st[i] = true;sum -= a[i];ans--;}}if (!flag)break;}cout << cnt;
}作者：你好A
链接：https://www.acwing.com/solution/content/140217/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第72场周赛

AcWing 4625. 压缩文件

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 1e6;int c[N];bool cmp(int i, int j)
{return i > j;
}int main()
{LL n, m, t1 = 0;cin >> n >> m;int a, b;for (int i = 0; i < n; i ++ ) cin >> a >> b, c[i] = a - b, t1 += a;sort(c, c + n, cmp);if (t1 <= m){puts("0");return 0;}for (int i = 0; i < n; i ++ ){t1 -= c[i];if (t1 <= m){cout << i + 1;return 0;}}cout << -1;return 0;
}作者：大学才
链接：https://www.acwing.com/solution/content/141592/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

AcWing 4626. 最小移动距离

第 75 场周赛

AcWing 4710. 局部和

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;int sum[n+1];sum[0]=0;for(int i=1;i<n;i++){cin>>x;sum[i]=sum[i-1]+x;}cin>>k>>d;cout<<sum[d-1]-sum[k-1]<<endl;return 0;
}

AcWing 4711. 排队

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z,t;
char ch;
string str;
vector<int>v[N];
struct node
{string name;int quanxian;int cixu;
}stu[N];bool cmp(node a, node b){if(a.quanxian!=b.quanxian){return a.quanxian<b.quanxian;}else if(a.quanxian==b.quanxian){return a.cixu<b.cixu;}
}
int main() {cin>>n;for(int i=0;i<n;i++){cin>>stu[i].name;stu[i].cixu=i;cin>>str;if(str=="rat"){stu[i].quanxian=1;}else if(str=="woman"){stu[i].quanxian=2;}else if(str=="child"){stu[i].quanxian=2;}else if(str=="man"){stu[i].quanxian=4;}else{stu[i].quanxian=5;}}sort(stu,stu+n,cmp);for(int i=0;i<n;i++){cout<<stu[i].name<<endl;}return 0;
}

AcWing 4712. 变换树根

==种植险=

No.4 秋招每日一题：

LeetCode 1282. 用户分组

class Solution {
public:vector<vector<int>> groupThePeople(vector<int>& g) {map<int, vector<int>> vt;vector<vector<int>> res;for (int i = 0; i < g.size(); i ++) {vt[g[i]].push_back(i);if (vt[g[i]].size() == g[i]) {res.push_back(vt[g[i]]);vt[g[i]].clear();}}return res;}
};

LeetCode 768. 最多能完成排序的块 II：经典题目

//自己写的比较复杂：class Solution {
public:int maxChunksToSorted(vector<int>& arr) {//双指针、首先找到比i位置小的j，然后i++ 再次寻找int res=0;int maxx=0;int j=0;vector<int>ans;for(int i=0;i<arr.size();i++){maxx=i;for(j=i;j<arr.size();j++){//找到比i大的位置，if(arr[j]>arr[maxx])maxx=j;//找到比i小的位置，if(arr[j]<arr[i]){ans.push_back(j);for(auto pos:ans){if(pos>maxx)arr[i]=arr[maxx];}}}if(ans.size()==0){res++;continue;}int weizhi=ans[ans.size()-1];i=weizhi;res++;ans.clear();}return res;}
};

4405：统计子矩阵：得到子矩阵方法

LeetCode 1346. 检查整数及其两倍数是否存在

class Solution {
public:bool checkIfExist(vector<int>& arr) {int flag=0;for(int i=0;i<arr.size();i++){int a = arr[i];for(int j=arr.size()-1;j>=0;j--){if(j==i)continue;if(arr[j]*2==arr[i]){flag=1;break;}}if(flag==1)break;}if(flag==1){return true;}else{return false;}}
};

LeetCode 1342. 将数字变成 0 的操作次数

class Solution {
public:int numberOfSteps(int num) {int sum=0;while(num!=0){if(num%2==0){num=num/2;sum++;}else{num--;sum++;}}return sum;}
};

1343. 大小为 K 且平均值大于等于阈值的子数组数目：滑动窗口or前缀和。

该题为滑动窗口or前缀和。滑动窗口：
class Solution {
public:int numOfSubarrays(vector<int>& arr, int k, int threshold) {int n = arr.size();// 期望最小和int exp = k * threshold;int sum = 0;int res = 0;// 初始窗口for (int i = 0; i < k; ++i){sum += arr[i];}res += sum >= exp;for (int i = k; i < n; ++i){sum += -arr[i-k] + arr[i];res += sum >= exp;}return res;}
};作者：ffreturn
链接：https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/solution/1343-czhong-gui-zhong-ju-de-hua-dong-chu-tacb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。前缀和：
class Solution {
public:int numOfSubarrays(vector<int>& arr, int k, int threshold) {int n = arr.size();int sum[n+1];sum[0] = 0;//求前缀和for(int i = 1;i <= n;i++)sum[i] = sum[i-1] + arr[i-1];int ans = 0;for(int i = 0;i+k <= n;i++){if((sum[i+k] - sum[i]) >= k*threshold){ans++;}}return ans;}
};

LeetCode 1359. 有效的快递序列数目：排列组合

using LL = long long;class Solution {
private:static constexpr int mod = 1000000007;public:int countOrders(int n) {if (n == 1) {return 1;}int ans = 1;for (int i = 2; i <= n; ++i) {ans = (LL)ans * (i * 2 - 1) % mod * i % mod;}return ans;}
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/count-all-valid-pickup-and-delivery-options/solution/you-xiao-de-kuai-di-xu-lie-shu-mu-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

LeetCode 1370. 上升下降字符串

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {string s="leetcode";set<char>sc;map<char,int>mp;for(auto i:s){mp[i]++;sc.insert(i);}string newss = "";for(auto i:sc)newss=newss+i;string fanss = newss;reverse(fanss.begin(),fanss.end());int ans=0;string resss="";while(ans!=s.size()){for(auto i:newss){if(mp[i]>0){resss=resss+i;mp[i]--;ans++;}} for(auto i:fanss){if(mp[i]>0){resss=resss+i;mp[i]--;ans++;}} }cout<<resss<<endl;return 0;
}

LeetCode 1329. 将矩阵按对角线排序

class Solution {
public:vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {int n=mat.size();int m = mat[0].size();//先处理行：for(int i=0;i<n;i++){//对于第一行的第一个来说：int j = 0;vector<int>vv;for(int p=i,q=j ;p<n,q<m;p++,q++){vv.push_back(mat[p][q]);}sort(vv.begin(),vv.end());int s=0;for(int p=i,q=j ;p<n,q<m;p++,q++){mat[p][q]=vv[s++];}}//再处理列：for(int j=1;j<m;j++){int i=0;vector<int>vv;for(int p=i,q=j ;p<n,q<m;p++,q++){vv.push_back(mat[p][q]);}sort(vv.begin(),vv.end());int s=0;for(int p=i,q=j ;p<n,q<m;p++,q++){mat[p][q]=vv[s++];}}return mat;}
};

LeetCode 1385. 两个数组间的距离值

class Solution {
public:int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {int res = 0;for(int i=0;i<arr1.size();i++){int a = arr1[i];int flag = 0;for(auto j:arr2){if(abs(a-j)<=d){flag = 1;break;}}if(flag==0)res++;}return res;}
};

LeetCode 1386. 安排电影院座位

class Solution {
public:int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {int res = 0;int flag = 0;unordered_map<int,unordered_set<int>>sc;for(auto s:reservedSeats){int a =s[0];sc[a].insert(s[1]);}for(auto s:sc){int flag = 0;//对于每一 行来说：if( s.second.count(2)==0 &&s.second.count(3)==0&&s.second.count(5)==0&&s.second.count(4)==0){res++;flag =1;}if( s.second.count(6)==0 &&s.second.count(7)==0&&s.second.count(8)==0&&s.second.count(9)==0){res++;flag =1;}if(4,5,6,7==0 && flag == 0){res++}}res = res + 2*(n-reservedSeats.size());return res;}
};

1387. 将整数按权重排序

主要是 关于 cmp的 编写；； 可以这样 当然也可以 那样：

sort(v.begin(), v.end(), [&] (int u, int v) {
if (getF(u) != getF(v)) return getF(u) < getF(v);
else return u < v;
});

class Solution {
public:static int getC(int x){int res=0;while(x!=1){if(x%2==0)x=x/2;else x=x*3+1;res++;}return res;}static bool cmp(int x,int y){if(getC(x)!=getC(y)){return getC(x)<getC(y);}else{return x<y;}}int getKth(int lo, int hi, int k) {vector<int>ans;for(int i=lo;i<=hi;i++){ans.push_back(i);}sort(ans.begin(),ans.end(),cmp);return ans[k-1];}
};

public:
vector<vector> diagonalSort(vector<vector>& mat) {
int n=mat.size();
int m = mat[0].size();
//先处理行：
for(int i=0;i<n;i++){
//对于第一行的第一个来说：
int j = 0;
vectorvv;
for(int p=i,q=j ;p<n,q<m;p++,q++){
vv.push_back(mat[p][q]);
}
sort(vv.begin(),vv.end());
int s=0;
for(int p=i,q=j ;p<n,q<m;p++,q++){
mat[p][q]=vv[s++];
}
}

    //再处理列：for(int j=1;j<m;j++){int i=0;vector<int>vv;for(int p=i,q=j ;p<n,q<m;p++,q++){vv.push_back(mat[p][q]);}sort(vv.begin(),vv.end());int s=0;for(int p=i,q=j ;p<n,q<m;p++,q++){mat[p][q]=vv[s++];}}return mat;
}

};

## LeetCode 1385. 两个数组间的距离值```c++
class Solution {
public:int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {int res = 0;for(int i=0;i<arr1.size();i++){int a = arr1[i];int flag = 0;for(auto j:arr2){if(abs(a-j)<=d){flag = 1;break;}}if(flag==0)res++;}return res;}
};

LeetCode 1386. 安排电影院座位

class Solution {
public:int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {int res = 0;int flag = 0;unordered_map<int,unordered_set<int>>sc;for(auto s:reservedSeats){int a =s[0];sc[a].insert(s[1]);}for(auto s:sc){int flag = 0;//对于每一 行来说：if( s.second.count(2)==0 &&s.second.count(3)==0&&s.second.count(5)==0&&s.second.count(4)==0){res++;flag =1;}if( s.second.count(6)==0 &&s.second.count(7)==0&&s.second.count(8)==0&&s.second.count(9)==0){res++;flag =1;}if(4,5,6,7==0 && flag == 0){res++}}res = res + 2*(n-reservedSeats.size());return res;}
};

1387. 将整数按权重排序

主要是 关于 cmp的 编写；； 可以这样 当然也可以 那样：

sort(v.begin(), v.end(), [&] (int u, int v) {
if (getF(u) != getF(v)) return getF(u) < getF(v);
else return u < v;
});

class Solution {
public:static int getC(int x){int res=0;while(x!=1){if(x%2==0)x=x/2;else x=x*3+1;res++;}return res;}static bool cmp(int x,int y){if(getC(x)!=getC(y)){return getC(x)<getC(y);}else{return x<y;}}int getKth(int lo, int hi, int k) {vector<int>ans;for(int i=lo;i<=hi;i++){ans.push_back(i);}sort(ans.begin(),ans.end(),cmp);return ans[k-1];}
};