A
谁家第一题放模板。
最大的小于 x 的可以用 lower_bound 的前驱做到。
#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
using namespace std;
const int CHECK=0,FIL=1;int read();
set<int> s;
int n,op,a;
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("set.in","r",stdin);
FRE freopen("set.out","w",stdout);
auto it=s.begin();
n=read();while(n--){
op=read();a=read();switch(op){
case 1:
s.insert(a);
break;
case 2:
s.erase(a);
break;
case 3:
if(s.count(a)) printf("yes\n");
else printf("no\n");
break;
case 4:
it=s.lower_bound(a);
if(it==s.end()) printf("-1\n");
else printf("%d\n",*it);
break;
case 5:
it=s.upper_bound(a);
if(it==s.end()) printf("-1\n");
else printf("%d\n",*it);
break;
case 6:
it=s.upper_bound(a);
if(it==s.begin()) printf("-1\n");
else printf("%d\n",*prev(it));
break;
case 7:
it=s.lower_bound(a);
if(it==s.begin()) printf("-1\n");
else printf("%d\n",*prev(it));
break;
}}
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
B
手搓一下可以发现过程是这样的：
- 第一个人一直打牌（其他人跳过）直到他只剩下一张
- 然后交给逆时针方向第一个牌数大于 1 的人出牌。
- 以此类推，最后如果都没了就最后一个出牌的那个结束游戏。
按题意模拟即可。
#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
using namespace std;
const int CHECK=0,FIL=1;int read();
set<int> s;
int n,op,a;
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("set.in","r",stdin);
FRE freopen("set.out","w",stdout);
auto it=s.begin();
n=read();while(n--){
op=read();a=read();switch(op){
case 1:
s.insert(a);
break;
case 2:
s.erase(a);
break;
case 3:
if(s.count(a)) printf("yes\n");
else printf("no\n");
break;
case 4:
it=s.lower_bound(a);
if(it==s.end()) printf("-1\n");
else printf("%d\n",*it);
break;
case 5:
it=s.upper_bound(a);
if(it==s.end()) printf("-1\n");
else printf("%d\n",*it);
break;
case 6:
it=s.upper_bound(a);
if(it==s.begin()) printf("-1\n");
else printf("%d\n",*prev(it));
break;
case 7:
it=s.lower_bound(a);
if(it==s.begin()) printf("-1\n");
else printf("%d\n",*prev(it));
break;
}}
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
C
容易想到先把初始的连通块缩点。
易证明一定有一种最优方案是一直操作一个点，所以枚举操作的那个点然后模拟即可。
#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define MX 505
using namespace std;
const int CHECK=0,FIL=1;int read();
int res,col[MX],n,m,c[MX],dis[MX],ck[MX][MX];
vector<int> v[MX],g[MX];queue<int> q;
void dfs(int t,int rt){
col[t]=rt;c[t]=2;
for(auto i:v[t])
if(c[i]==col[0]) dfs(i,rt);
}
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("tutu.in","r",stdin);
FRE freopen("tutu.out","w",stdout);
res=n=read();m=read();
for(int i=1;i<=n;i++) c[i]=read();
while(m--){
int a=read();int b=read();
v[a].push_back(b);
v[b].push_back(a);
}
for(int i=1;i<=n;i++){
if(c[i]>=2) continue;
col[0]=c[i];dfs(i,i);
}
for(int I=1;I<=n;I++) for(auto J:v[I]){
int i=col[I],j=col[J];
if(i!=j && !(ck[i][j]++)){g[i].push_back(j);}
}
for(int i=1;i<=n;i++){
if(col[i]!=i) continue;
int cnt=0;
for(int j=1;j<=n;j++) dis[j]=-1;
dis[i]=0;q.push(i);
while(q.size()){
int t=q.front();q.pop();
cnt=max(cnt,dis[t]);
for(auto j:g[t]){
if(dis[j]>=0) continue;
dis[j]=dis[t]+1;q.push(j);
}
}
res=min(res,cnt);
}printf("%d\n",res);
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
D
先用 Tarjan 找环（割边）。
根据题目给的性质，把环缩点后一定是棵树。
求树的最大独立集是容易的。
对于每个节点就是在环上 dp，断环为链然后枚举第一个的状态即可。
//w** & cy*
#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define int long long
#define MX 500005
#define MM 550005
using namespace std;
const int CHECK=0,FIL=1;int read();
int cnt=1,cwt=1,hd[MX],hd2[MX],n,m;
int low[MX],dfn[MX];
int f[MX][2],a[MX],nxt[MX];
struct eg{
int x,y,z;
//from to next
}v[MM*2],g[MM*2];
void add(int x,int y){v[++cnt].x=x;v[cnt].y=y;v[cnt].z=hd[x];hd[x]=cnt;}
void add2(int x,int y){g[++cwt].x=x;g[cwt].y=y;g[cwt].z=hd2[x];hd2[x]=cwt;}
void tarj(int t,int faa){
low[t]=dfn[t]=++cnt;nxt[t]=t;
for(int o=hd[t];o;o=v[o].z){
int i=v[o].y;
if(faa==i) continue;
if(!dfn[i]){
tarj(i,t);
low[t]=min(low[t],low[i]);
if(low[i]<=dfn[t]){
nxt[t]=i;
}else{
add2(t,i);
}
}else{
low[t]=min(low[t],dfn[i]);
if(nxt[t]==t) nxt[t]=i;
}
}
//cout<<t<<"("<<faa<<") "<<dfn[t]<<' '<<low[t]<<'\n';
}
int solve(int t,int op);
int calcu(int t,int op){
int rep=0;
for(int o=hd2[t];o;o=g[o].z)
rep+=solve(g[o].y,op);
return rep;
}
int solve(int t,int op){
if(f[t][op]>=0) return f[t][op];
int x=0,y=0,z=0,i;
if(!op){
x=-1e15,y=calcu(t,1)+a[t];
i=nxt[t];while(i!=t){
z=max(x,y)+calcu(i,0);
y=x+calcu(i,1)+a[i];x=z;
i=nxt[i];
}
if(nxt[t]==t) x=y;
f[t][op]=max(f[t][op],x);
}
x=calcu(t,0),y=-1e15;
i=nxt[t];while(i!=t){
z=max(x,y)+calcu(i,0);
y=x+calcu(i,1)+a[i];x=z;
i=nxt[i];
}f[t][op]=max(f[t][op],max(x,y));
//cout<<t<<' '<<op<<' '<<f[t][op]<<'\n';
return f[t][op];
}
signed main(){
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
FRE freopen("bamboo.in","r",stdin);
FRE freopen("bamboo.out","w",stdout);
n=read();m=read();
for(int i=1;i<=n;i++) a[i]=read();
while(m--){
int x=read();int y=read();
add(x,y);add(y,x);
}
cnt=0;tarj(1,0);
for(int i=1;i<=n;i++) f[i][0]=f[i][1]=-1;
//for(int i=1;i<=n;i++) cout<<nxt[i]<<' '; cout<<'\n';
printf("%lld\n",solve(1,0));
return 0;
}
int read(){
int Ca=0;char Cr=' ';int Cf=1;
while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
星战
出边为 1 就一定有基环树，所以只考虑出边为 1。
发现入度更好维护，所以考虑给每个点随机赋值，对于每个点维护通向这个点的点的权值之和。
如果这些和等于每个点的权值和那么很大很大概率每个点的出边为 1。
Censoring S
开一个栈维护后 m 位的哈希值即可。
销售基因链
正向反向各建一个 Trie。
每次询问找到节点后实际上就是询问有多少的点同时在两棵树的某个子树中。
把 Trie 的节点按照 dfs 序重新编号就可以吧子树转换成区间。
然后即可离线二维数点。
HH 的项链 / 采花
考虑把询问按照右端点排序。
然后发现每个值只有最后一个位置是有用的。
所以上个树状数组即可解决。
采花就是换成维护最后两个位置。