B题
双指针+贪心，先按照权值排序，对于每个l，找到最近符合条件的r
注意如果可以不取A，那就别取A
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e6+10; int cnt,n,k,anum,num,st[N],a[N]; struct node{ int id,x,flag; }s[N]; bool cmp(node a,node b){ return a.x<b.x; } bool check(){ if(num==n&&anum<=k) return true; return false; } void add(int x){ if(st[s[x].id]==1&&a[s[x].id]) anum--;//之前存在的那个A没必要取 st[s[x].id]++; if(st[s[x].id]==1) num++; if(s[x].flag) a[s[x].id]=1; if(st[s[x].id]==1&&a[s[x].id]) anum++;//只有自己是唯一的并且是A才必须取，不然没有必要取 } void sub(int x){ if(st[s[x].id]==1&&a[s[x].id]) anum--; st[s[x].id]--; if(st[s[x].id]==0) num--; if(s[x].flag) a[s[x].id]=0; if(st[s[x].id]==1&&a[s[x].id]) anum++; } int main(){ ios::sync_with_stdio(false); cin>>n>>k; int i,j; for(i=1;i<=n;i++){ for(j=1;j<=5;j++){ int x; cin>>x; if(j==1){ s[++cnt]={i,x,1}; } else{ s[++cnt]={i,x,0}; } } } sort(s+1,s+1+cnt,cmp); int r=1; int ans=1e9; for(i=1;i<=cnt;i++){ if(i>1){ sub(i-1); } while(r<=cnt&&!check()){ add(r); r++; } if(check()){ ans=min(ans,s[r-1].x-s[i].x); } } cout<<ans<<endl; return 0; }
C题
暴力做
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e6+10; int n,k,R; int x[N],y[N],r[N]; int dx[N],dy[N]; int ans; bool check(int i,int j){ int dis=(x[i]-dx[j])*(x[i]-dx[j])+(y[i]-dy[j])*(y[i]-dy[j]); if(dis>(R+r[i])*(R+r[i])) return false; return true; } void dfs(int u){ if(u==k+1){ int i; int cnt=0; for(i=1;i<=n;i++){ int flag=0; for(int j=1;j<=k;j++){ if(check(i,j)){ flag=1; } } cnt+=flag; } ans=max(ans,cnt); return ; } int i,j; for(i=-7;i<=7;i++){ for(j=-7;j<=7;j++){ dx[u]=i,dy[u]=j; dfs(u+1); } } } int main(){ ios::sync_with_stdio(false); cin>>n>>k>>R; int i; for(i=1;i<=n;i++){ cin>>x[i]>>y[i]>>r[i]; } dfs(1); cout<<ans<<endl; return 0; }
D题
签到
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=4e5+10; int main(){ ios::sync_with_stdio(false); int n; cin>>n; int i; int d=n; int res=0; while(d){ res+=(d%10); d/=10; } for(i=n+1;;i++){ int sum=0; int tmp=i; while(tmp){ sum+=(tmp%10); tmp/=10; } if(res==sum){ cout<<i<<endl; return 0; } } return 0; }
E题
经典套路，维护最近相同数的位置，这里可以借用链表的思想，这样每次只要更改两个位置即可，之后就是线段树查询区间最大值是否大于l
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e6+10; int n,q,pos[N]; int a[N],lst[N],nxt[N]; struct node{ int l,r; int mx; }tr[N<<2]; void pushup(int u){ tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx); } void build(int u,int l,int r){ if(l==r){ tr[u]={l,r,lst[l]}; } else{ tr[u]={l,r}; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } } void modify(int u,int l,int x){ if(tr[u].l==tr[u].r){ tr[u].mx=x; return ; } int mid=tr[u].l+tr[u].r>>1; if(l<=mid){ modify(u<<1,l,x); } else{ modify(u<<1|1,l,x); } pushup(u); } int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r){ return tr[u].mx; } int mid=tr[u].l+tr[u].r>>1; int ans=0; if(l<=mid){ ans=max(ans,query(u<<1,l,r)); } if(r>mid) ans=max(ans,query(u<<1|1,l,r)); return ans; } int main(){ ios::sync_with_stdio(false); cin>>n>>q; int i; for(i=1;i<=n;i++){ cin>>a[i]; lst[i]=pos[a[i]]; pos[a[i]]=i; } for(i=1;i<N;i++){ pos[i]=n+1; } for(i=n;i>=1;i--){ nxt[i]=pos[a[i]]; pos[a[i]]=i; } build(1,1,n); while(q--){ int opt; cin>>opt; if(opt==1){ int x; cin>>x; if(nxt[x]!=n+1){ modify(1,nxt[x],lst[x]); } lst[nxt[x]]=lst[x]; nxt[lst[x]]=nxt[x]; modify(1,x,0); } else{ int l,r; cin>>l>>r; if(query(1,l,r)>=l){ cout<<1<<endl; } else{ cout<<0<<endl; } } } return 0; }
F题
贪心题，因为本题每个串都有至少一个#，所以答案要不是0要不是无穷，因为中间的部分可以无限延长。
那么只要比较前后缀即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e6+10; string s[N]; string pre[N]; string suf[N]; bool cmp(string a,string b){ return a.size()>b.size(); } bool check1(int x,int y){ int i; for(i=0;i<pre[y].size();i++){ if(pre[x][i]!=pre[y][i]) return false; } return true; } bool check2(int x,int y){ int i; for(i=0;i<suf[y].size();i++){ if(suf[x][i]!=suf[y][i]) return false; } return true; } int main(){ ios::sync_with_stdio(false); int n; cin>>n; int i; for(i=1;i<=n;i++){ cin>>s[i]; } for(i=1;i<=n;i++){ for(int j=0;j<(int)s[i].size();j++){ if(s[i][j]!='#'){ pre[i]+=s[i][j]; } else{ break; } } } for(i=1;i<=n;i++){ for(int j=(int)s[i].size()-1;j>=0;j--){ if(s[i][j]!='#'){ suf[i]+=s[i][j]; } else{ break; } } } sort(pre+1,pre+n+1,cmp); sort(suf+1,suf+1+n,cmp); int flag=0; for(i=2;i<=n;i++){ if(!check1(i-1,i)){ flag=1; break; } } for(i=2;i<=n;i++){ if(flag) break; if(!check2(i-1,i)){ flag=1; break; } } if(flag){ cout<<0<<endl; } else{ cout<<-1<<endl; } return 0; }
G题
可以用并查集或者dfs，因为一个集合里面的人取值要相同并且是他们中的最大值
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e6+10; int n,m; int a[N]; ll f[N],st[N]; int h[N],ne[N],e[N],idx; int cnt; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int fa){ f[u]=a[u]; st[u]=1; int i; cnt++; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==fa||st[j]) continue; dfs(j,u); f[u]=max(f[u],f[j]); } } int main(){ ios::sync_with_stdio(false); int i; cin>>n>>m; memset(h,-1,sizeof h); for(i=1;i<=n;i++){ cin>>a[i]; } for(i=1;i<=m;i++){ int x,y; cin>>x>>y; add(x,y); add(y,x); } ll res=0; for(i=1;i<=n;i++){ if(!st[i]){ cnt=0; dfs(i,-1); res+=cnt*f[i]; } } cout<<res<<endl; return 0; }
H题
最多只要修改一次就行了，第一种找到可以拆分的两位数拆分，第二种找到可以合并的一位数合并
如果这两种都不行，那就不行
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e6; string s; int main(){ ios::sync_with_stdio(false); cin>>s; int i; int flag=-1; for(i=0;i<(int)s.size();i++){ int fc=s[i]-'a'+1; if(fc>10&&fc!=20){ flag=i; } } if(flag!=-1){ string res=""; for(i=0;i<(int)s.size();i++){ if(i!=flag){ res+=s[i]; } else{ int fc=s[i]-'a'+1; int d=fc%10; fc/=10; res+='a'+fc-1; res+='a'+d-1; } } cout<<res<<endl; } else{ string res=""; for(i=0;i<(int)s.size()-1;i++){ int x=s[i]-'a'+1; int y=s[i+1]-'a'+1; if(x>=10||y>=10) continue; if(x*10+y<=26){ flag=i; break; } } if(flag!=-1){ for(i=0;i<(int)s.size();i++){ if(i!=flag){ res+=s[i]; } else{ int x=s[i]-'a'+1; int y=s[i+1]-'a'+1; res+='a'+x*10+y-1; i++; } } cout<<res<<endl; } else{ cout<<-1<<endl; } } return 0; }
I题
贪心，只要能出现合并的就合并，这样一定不劣，因为每次多一个相同只会最多多一个，而我们合并也多了一个
所以只要用map记录最近的与我相同的位置，一旦合并成功，就把之前的map信息删除
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e6+10; int a[N]; map<int,int> m1; int main(){ ios::sync_with_stdio(false); int i; int n; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; int ans=0; for(i=1;i<=n;i++){ if(m1[a[i]]){ m1.clear(); ans++; m1[a[i]]=1; } else{ m1[a[i]]++; } } cout<<ans<<endl; return 0; }
J题
思维博弈，注意特判1
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e6; int a[N]; int main(){ ios::sync_with_stdio(false); int n; int i; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; if(n==1&&(a[1]%2==1)){ cout<<"NiuNiu"<<endl; return 0; } if(n%2==0){ int cnt=0; for(i=1;i<=n;i++){ if(a[i]%2==0){ cnt++; } } if(cnt<=1){ cout<<"NiuNiu"<<endl; return 0; } } cout<<"NiuMei"<<endl; return 0; }