http://codeforces.com/contest/915
A：水题
#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=300000+10,maxn=400000+10,inf=0x3f3f3f3f; int a[N]; int main() { int n,k; scanf("%d%d",&n,&k); for(int i=0;i<n;i++)scanf("%d",&a[i]); sort(a,a+n); for(int i=n-1;i>=0;i--) { if(k%a[i]==0) { printf("%d ",k/a[i]); return 0; } } return 0; } /******************** ********************/
B：两侧贪心即可
#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=300000+10,maxn=400000+10,inf=0x3f3f3f3f; int main() { int n,pos,l,r; scanf("%d%d%d%d",&n,&pos,&l,&r); if(l==1&&r==n)printf("%d ",0); else if(l==1&&r!=n)printf("%d ",abs(r-pos)+1); else if(l!=1&&r==n)printf("%d ",abs(pos-l)+1); else { if(pos<=l)printf("%d ",r-pos+2); else if(pos>=r)printf("%d ",pos-l+2); else printf("%d ",min(2*r-l-pos+2,r+pos-2*l+2)); } return 0; } /******************** ********************/
C：给你两个数，要求重拍使得第一个数小于第二个数且最大
先记录下1中出现的各个数字个数，和第二个数字挨个比较，从当前位往小遍历，填入最大的，但是会有一个问题，可能会出现不能填的情况，比如325,324，那么我们需要往前找第一个能减小的地方即可
#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=300000+10,maxn=400000+10,inf=0x3f3f3f3f; int num[20]; int main() { fio; string a,b; cin>>a>>b; if(a.size()<b.size()) { sort(a.begin(),a.end()); reverse(a.begin(),a.end()); cout<<a<<" "; } else { for(int i=0;i<a.size();i++) num[a[i]-'0']++; a=string(a.size(),'a'); bool mi=0; for(int i=0;i<b.size();i++) { int j=b[i]-'0'; if(mi)j=9; for(;j>=0;j--) { if(num[j]>0) { a[i]=j+'0'; num[j]--; if(b[i]-'0'!=j)mi=1; break; } } if(a[i]=='a') { while(!mi&&i>=0) { i--; num[a[i]-'0']++; for(int j=b[i]-'0'-1;j>=0;j--) { if(num[j]>0) { a[i]=j+'0'; num[j]--; mi=1; break; } } } } } cout<<a<<" "; } return 0; } /******************** 325 324 ********************/
D：给你一张有向无环图，问你能不能删一条边使得，图中没有环，
我们先判断有没有环，有环就抠出来，然后挨个删边，判断还有没有环，因为是简单环，所以复杂度不会超过nm
#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=500+10,maxn=400000+10,inf=0x3f3f3f3f; vector<int>v[N]; int ma[N][N]; int in[N],tein[N]; int n,m; int topo() { queue<int>q; for(int i=1;i<=n;i++) if(!in[i]) q.push(i); int num=0; while(!q.empty()) { int u=q.front(); q.pop(); num++; for(int i=1;i<=n;i++) { if(ma[u][i]) { in[i]--; ma[u][i]--; if(in[i]==0)q.push(i); } } } return num; } int topo1(int a,int b) { queue<int>q; for(int i=1;i<=n;i++) if(in[i]&&!tein[i]) q.push(i); int num=0; while(!q.empty()) { int u=q.front(); q.pop(); num++; for(int i=0;i<v[u].size();i++) { int x=v[u][i]; if(u==a&&x==b)continue; tein[x]--; if(tein[x]==0)q.push(x); } } return num; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); ma[a][b]++; in[b]++; } int ans=topo(); if(ans==n)puts("YES"); else { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(ma[i][j]) v[i].pb(j); for(int i=1;i<=n;i++) { for(int j=0;j<v[i].size();j++) { for(int k=1;k<=n;k++)tein[k]=in[k]; tein[v[i][j]]--; // printf("%d %d %d ",i,v[i][j],topo1(i,v[i][j])); if(topo1(i,v[i][j])==n-ans)return 0*puts("YES"); } } puts("NO"); } return 0; } /******************** 3 4 1 2 2 3 3 2 1 3 ********************/
E：第一种操作，把一段区间变成1，第二种，把一段区间变成0
由于数据范围1到1e9，所以我们需要离散化，离散化之后可能会出现边界问题，那么我们把所有区间和单个点都建成一颗线段树，然后维护即可
#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=300000+10,maxn=400000+10,inf=0x3f3f3f3f; struct op{ int l,r,k; }p[N]; int Hash[N*2]; int value[N<<4],lazy[N<<4],te[N<<4],dis[N<<2]; void pushup(int rt) { value[rt]=value[rt<<1]+value[rt<<1|1]; } void pushdown(int l,int r,int rt) { if(lazy[rt]) { if(lazy[rt]==1)value[rt<<1]=value[rt<<1|1]=0; else { int m=(l+r)>>1; value[rt<<1]=te[rt<<1]; value[rt<<1|1]=te[rt<<1|1]; } lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; lazy[rt]=0; } } void build(int l,int r,int rt) { if(l==r) { // printf("%d ",dis[l]); value[rt]=dis[l]; return ; } int m=(l+r)>>1; build(ls); build(rs); pushup(rt); } void update(int L,int R,int op,int l,int r,int rt) { if(L<=l&&r<=R) { if(op==1)value[rt]=0; else value[rt]=te[rt]; lazy[rt]=op; return ; } pushdown(l,r,rt); int m=(l+r)>>1; if(L<=m)update(L,R,op,ls); if(m<R)update(L,R,op,rs); pushup(rt); // printf("%d %d %d ",l,r,value[rt]); } void dfs(int l,int r,int rt) { // printf("%d-%d-%d ",l,r,value[rt]); te[rt]=value[rt]; if(l==r)return ; int m=(l+r)>>1; dfs(ls);dfs(rs); } int main() { int n,q,cnt=0; scanf("%d%d",&n,&q); for(int i=0;i<q;i++) { scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].k); Hash[cnt++]=p[i].l; Hash[cnt++]=p[i].r; } Hash[cnt++]=1,Hash[cnt++]=n; sort(Hash,Hash+cnt); cnt=unique(Hash,Hash+cnt)-Hash; int kn=0; for(int i=0;i<cnt-1;i++) { dis[++kn]=1; dis[++kn]=Hash[i+1]-Hash[i]-1; } dis[++kn]=1; build(1,kn,1); dfs(1,kn,1); // update(1,3,1,1,kn,1); // printf("%d ",value[1]); for(int i=0;i<q;i++) { int l=lower_bound(Hash,Hash+cnt,p[i].l)-Hash; int r=lower_bound(Hash,Hash+cnt,p[i].r)-Hash; update(2*l+1,2*r+1,p[i].k,1,kn,1); // printf("%d %d ",l*2+1,r*2+1); printf("%d ",value[1]); } return 0; } /******************** ********************/
F：给你一棵树，每点有一个值，两点之间的价值是这条链上的最大值-最小值，求每两个点之间的价值和
直接算不好算，所以我们考虑对于每个点算贡献，每个点的贡献是它在树上的最大作用范围，并查集维护，先把边从小到大排一遍，然后依次加边，每次加边计算左右两侧的最大值，然后乘上左边节点数和右边节点数，然后更新节点数，最大值，最小值同理
#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=1000000+10,maxn=400000+10,inf=0x3f3f3f3f; struct edge{ int x,y; }e[N]; int a[N],father[N],sz[N]; int ma[N],mi[N]; int Find(int x) { return x==father[x]?x:father[x]=Find(father[x]); } bool cmp1(edge e1,edge e2) { return max(a[e1.x],a[e1.y])<max(a[e2.x],a[e2.y]); } bool cmp2(edge e1,edge e2) { return min(a[e1.x],a[e1.y])>min(a[e2.x],a[e2.y]); } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<n;i++) { scanf("%d%d",&e[i].x,&e[i].y); } for(int i=1;i<=n;i++)ma[i]=a[i],father[i]=i,sz[i]=1; sort(e+1,e+n,cmp1); ll ans=0; for(int i=1;i<n;i++) { int x=e[i].x,y=e[i].y; int fx=Find(x),fy=Find(y); //printf("%d %d ",fx,fy); ans+=(ll)max(ma[fx],ma[fy])*sz[fx]*sz[fy]; father[fy]=fx; sz[fx]+=sz[fy]; ma[fx]=max(ma[fx],ma[fy]); } //printf("%lld ",ans); for(int i=1;i<=n;i++)mi[i]=a[i],father[i]=i,sz[i]=1; sort(e+1,e+n,cmp2); for(int i=1;i<n;i++) { int x=e[i].x,y=e[i].y; int fx=Find(x),fy=Find(y); ans-=(ll)min(mi[fx],mi[fy])*sz[fx]*sz[fy]; father[fy]=fx; sz[fx]+=sz[fy]; mi[fx]=min(mi[fx],mi[fy]); } printf("%lld ",ans); return 0; } /******************** ********************/
G：如果一个数列全部gcd起来为1，那么就叫它good，给你n，k，要求算从1到k，假设第i个，求有多少个数列是good数列，而且每个值都是1到i，把这个当做bi，求∑（1，k）bi^i
先考虑单个i，要构造出这个数列，我们可以用容斥，对于gcd=1的我们每个点都可以任意选方案数是【i/1】，同理gcd=x，方案数是【i/x】（相当于每个先放x，然后乘上倍数，但是不能超过i）
但是gcd=1我们构造的方法可能会出现gcd！=1的情况，所有我们得删除其他的，比如gcd1-gcd2-gcd3+gcd6，那么就是μ(i)gcdi，μi就是莫比乌斯系数，我们可以先线性筛求出莫比乌斯系数，对于单个i的答案，我们先求出i的所有因子，然后i-1/j此时不能整除，我们加上所有的μ（j）*（【i+1/j】^n-【i/j】^n），（这是i+1和i的差值）最后答案就是求一个前缀和即可
#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=2000000+10,maxn=400000+10,inf=0x3f3f3f3f; int mu[N],prime[N]; bool mark[N]; void init() { mu[1]=1; int cnt=0; for(int i=2;i<N;i++) { if(!mark[i])prime[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt;j++) { int t=i*prime[j]; if(t>N)break; mark[t]=1; if(i%prime[j]==0){mu[t]=0;break;} else mu[t]=-mu[i]; } } } ll quick(ll a,ll b) { ll ans=1; while(b) { if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } ll f[N],ans[N]; int main() { init(); ll n,k; scanf("%lld%lld",&n,&k); for(int i=0;i<=k;i++)f[i]=quick(i,n); for(int i=1;i<=k;i++) { for(int j=1;j<=k;j++) { if(i*j>k)break; ans[i*j]+=mu[j]*(f[i]-f[i-1]); ans[i*j]%=mod; } } // for(int i=1;i<=k;i++)printf("%d ",ans[i]); for(int i=1;i<=k;i++)ans[i]=(ans[i-1]+ans[i])%mod; ll res=0; for(int i=1;i<=k;i++) { ans[i]=(ans[i]+mod)%mod; res=(res+(ans[i]^i))%mod; } printf("%lld ",res); return 0; } /******************** ********************/