A:水题,直接出答案(我因为括号打错地方wa了一发= =)
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=400000+10,inf=0x3f3f3f3f; int main() { ll k,n,w; scanf("%lld%lld%lld",&k,&n,&w); printf("%lld ",max(0ll,(1+w)*w/2*k-n)); return 0; } /******************** ********************/
B:给你n个数要求每个数不相同,而且只能加,问最少加多少
sbfor过去即可
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=400000+10,inf=0x3f3f3f3f; int a[N]; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",&a[i]); sort(a,a+n); ll ans=0; for(int i=1;i<n;i++) { if(a[i]<=a[i-1]) { ans+=a[i-1]-a[i]+1; a[i]=a[i-1]+1; } } printf("%lld ",ans); return 0; } /******************** ********************/
C:模拟题(我用了一个双端队列维护,其实vector,或者数组也可以),= =跑个1e6,没出答案就是死循环了
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=100+10,maxn=400000+10,inf=0x3f3f3f3f; deque<int>a,b; int main() { int n; scanf("%d",&n); int aa,bb; scanf("%d",&aa); for(int i=0;i<aa;i++) { int x; scanf("%d",&x); a.pb(x); } scanf("%d",&bb); for(int i=0;i<bb;i++) { int x; scanf("%d",&x); b.pb(x); } for(int i=1;i<1000000;i++) { if(a.size()==0) { printf("%d 2 ",i-1); return 0; } else if(b.size()==0) { printf("%d 1 ",i-1); return 0; } else { // printf("%d %d ",*a.begin(),*b.begin()); if(*a.begin()<*b.begin()) { b.push_back(*a.begin()); b.push_back(*b.begin()); b.pop_front(); a.pop_front(); } else { a.push_back(*b.begin()); a.push_back(*a.begin()); a.pop_front(); b.pop_front(); } } } puts("-1"); return 0; } /******************** ********************/
D:求a到b的因子个数的和
解法:在打素数表的时候每次对j不断除i,看能除几次就加上几,这样就算出了每个素数的答案的贡献,然后求一个前缀和即可
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=5000000+10,maxn=400000+10,inf=0x3f3f3f3f; ll ans[N]; bool prime[N]; void init() { int cnt=0; ans[1]=1; for(int i=2;i<N;i++) { if(!prime[i]) { cnt++; ans[i]=1; for(int j=i*2;j<N;j+=i) { prime[j]=1; int p=j; while(p%i==0)ans[j]++,p/=i; } } } // printf("%d ",cnt); } int main() { init(); for(int i=1;i<N;i++) ans[i]+=ans[i-1]; int t; scanf("%d",&t); while(t--) { int a,b; scanf("%d%d",&a,&b); printf("%lld ",ans[a]-ans[b]); } return 0; } /******************** ********************/
E:给你n个点,m个边,每个点上有a[i]个人,要求每个点上的人只能走到相邻点,问有没有一种走法,使得每个点上的人变成b[i]
解法:最大流,把每个点拆分成两个点,a,a'从s向每个a连边流量为a[i],从a'向t连边流量为b[i],a向a'连边流量为inf,如果a,b有一条边,那么就从a向b'连边,从b想a'连边流量也是inf,跑一次最大流就是答案了,然后按照反向边流量就是答案输出,有一点就是如果自己点上有些人没走的话,自身的也要输出,
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=2000+10,maxn=2000+10,inf=0x3f3f3f3f; struct edge{ int to,Next,c; }e[maxn]; int s,t,cnt,head[N],dis[N]; int a[N],b[N],ans[N][N]; pii p[N]; void add(int u,int v,int c) { e[cnt].to=v; e[cnt].c=c; e[cnt].Next=head[u]; head[u]=cnt++; e[cnt].to=u; e[cnt].c=0; e[cnt].Next=head[v]; head[v]=cnt++; } bool bfs() { memset(dis,-1,sizeof dis); dis[s]=1; queue<int>q; q.push(s); while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x];~i;i=e[i].Next) { int te=e[i].to; if(dis[te]==-1&&e[i].c>0) { dis[te]=dis[x]+1; q.push(te); } } } return dis[t]!=-1; } int dfs(int x,int mx) { if(x==t)return mx; int flow=0; for(int i=head[x];~i;i=e[i].Next) { int te=e[i].to,f; if(dis[te]==dis[x]+1&&e[i].c>0&&(f=dfs(te,min(mx-flow,e[i].c)))) { e[i].c-=f; e[i^1].c+=f; flow+=f; } } if(!flow)dis[x]=-2; return flow; } int max_flow() { int ans=0,f; while(bfs()) { while((f=dfs(s,inf)))ans+=f; } return ans; } void init() { memset(head,-1,sizeof head); cnt=0; } int main() { int n,m; scanf("%d%d",&n,&m); s=n*2+1,t=n*2+2; init(); int sum1=0,sum2=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum1+=a[i]; } for(int i=1;i<=n;i++) { scanf("%d",&b[i]); sum2+=b[i]; } for(int i=0;i<m;i++) { scanf("%d%d",&p[i].fi,&p[i].se); add(p[i].fi,n+p[i].se,inf); add(p[i].se,n+p[i].fi,inf); } for(int i=1;i<=n;i++) { add(s,i,a[i]); add(n+i,t,b[i]); add(i,i+n,inf); } int te=max_flow(); if(te!=sum1||te!=sum2)puts("NO"); else { puts("YES"); for(int i=1;i<4*m;i+=4) { if(e[i].c!=0)ans[p[i/4].fi][p[i/4].se]+=e[i].c; if(e[i+2].c!=0)ans[p[i/4].se][p[i/4].fi]+=e[i+2].c; // printf("%d %d %d %d ",e[i].c,e[i+2].c,p[i/4].fi,p[i/4].se);+ } for(int i=1;i<=n;i++) { int all=0; for(int j=1;j<=n;j++) all+=ans[i][j]; ans[i][i]=abs(all-a[i]); for(int j=1;j<=n;j++) printf("%d ",ans[i][j]); puts(""); } } return 0; } /******************** ********************/