Snowandraw.

9637

ycycyc

SuFame_Acwing_Only
Arthur_5

wuzgnm
ShallowHawk
Rain丶bow
Peter_5

starky
sourlf

SayonaraGzm

## Codeforces Global Round 17 A B C

### A. Anti Light’s Cell Guessing

• 参考代码：
#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
snow;
int t;
cin>>t;
while(t--){
int a,b;
cin>>a>>b;
if(a==1&&b==1){
cout<<0<<endl;
}
else if(a==1||b==1){
cout<<1<<endl;
}
else cout<<2<<endl;
}

return 0;
}


### B. Kalindrome Array

• 参考代码
#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
signed main(){
snow;
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int st=1,end=n;
while(a[st]==a[end]){
st++,end--;
}
if(st>=end){
cout<<"YES"<<endl;
continue;
}
int x1=a[st],x2=a[end];
int st1=st,end1=end;//复制一下当前的st和end,因为我们还要进行第二次操作。
bool success=false;
while(st1<end1){
if(a[st1]==a[end1])st1++,end1--;
else if(a[st1]==x1)st1++;
else if(a[end1]==x1)end1--;
else break;
if(st1>=end1)success=true;
}
st1=st,end1=end;
while(st1<end1){
if(a[st1]==a[end1])st1++,end1--;
else if(a[st1]==x2)st1++;
else if(a[end1]==x2)end1--;
else break;
if(st1>=end1)success=true;
}
if(success)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}


### C. Keshi Is Throwing a Party

• 参考代码
#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int n;
struct{
int a,b,c;
}nodes[N];
bool check(int x){
int num=0;
int l=0,r=x-1;//l表示左边有多少poorer,r表示右边有多少richer,一开始初始化第一个人那么左边为0,右边为x-1。
for(int i=1;i<=n;i++){
int b=nodes[i].b,c=nodes[i].c;
if(l<=b&&r<=c){num++;l++,r--;}//如果当前人可取我们才进行num++,以及l和r的更新。
}
if(num>=x)return true;//如果num>=x说明我能够取到不低于x的人数。
return false;
}
signed main(){
snow;
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
nodes[i].a=i;
cin>>nodes[i].c>>nodes[i].b;//b放poorer,c放richer。
}
int l=1,r=n;//人数在1~n中检验
while(l<r){
int mid=l+r+1>>1;
if(check(mid))l=mid;//如果当前人数满足,那么我们将区间延后。
else r=mid-1;
}
cout<<l<<endl;
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
unordered_map<int,int>S;
while(t--){
char x;
int y;
cin>>x>>y;
if(x=='I'){
S[y]++;
}
else{
if(S[y])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e5+10;
int a[N];
int son[N*31][2],idx;
void insert(int x){
int p=0;
for(int i=30;i>=0;i--){
int j=x>>i&1;
if(!son[p][j])son[p][j]=++idx;
p=son[p][j];
}
}
int search(int x){
int p=0;
int res=0;
for(int i=30;i>=0;i--){
int j=x>>i&1;
if(son[p][!j]){
res=(res<<1)+1;
p=son[p][!j];
}
else{
res<<=1;
p=son[p][j];
}
}
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
insert(a[i]);
}
int res=-2e9;
for(int i=1;i<=n;i++){
res=max(res,search(a[i]));
}
cout<<res<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Ne{
int l,r;
bool operator<(const Ne &W)const {
return l<W.l;
}
}nodes[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>nodes[i].l>>nodes[i].r;
}
sort(nodes,nodes+n);
int res=1;
int MA=nodes[0].r;
for(int i=1;i<n;i++){
if(nodes[i].l<=MA){
MA=max(MA,nodes[i].r);
}
else{
MA=nodes[i].r;
res++;
}
}
cout<<res<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int n,m,k,b;
const int N=35;
int f[N][N];
void init(){
for(int i=0;i<N;i++){
for(int j=0;j<=i;j++){
if(i==j)f[i][j]=1;
else f[i][j]=f[i-1][j]+f[i-1][j-1];
}
}
}
int dp(int x){
if(x==0)return 0;
int step=0;//存当前1的个数
int res=0;
vector<int>S;
while(x){
S.push_back(x%b);
x/=b;
}
for(int i=S.size()-1;i>=0;i--){//从大到小枚举
int num=S[i];
if(num){//如果有1
res+=f[i][k-step];//加上他是0的情况。
if(num>1){//如果是2那么可以全出来了,因为2>1&&2>0;
if(k-step-1>=0)res+=f[i][k-step-1];//除了他本身剩下的数求组合数
break;
}
else{
step++;
if(step>k)break;//如果step已经满了,说明当前数是1的位置已经在之前组合数宏计算过了,后面的也是一样的,所以
}//可以直接break;
}
if(!i&&step==k)res++;//一个比较难理解的点,因为每个数我们求的都是假设他是0,剩余数的组合数,那么这个条件主要是针对
}//的是全是0和1的数,最后还要加上他本身。
return res;
}
int main(){
cin>>n>>m>>k>>b;
init();//预处理组合数
cout<<dp(m)-dp(n-1)<<endl;//前缀和思想
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int t;
const int N=1510;
int idx,e[N],ne[N],h[N];
int w[N];
bool st[N];
int root;
int f[N][3];
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u){
f[u][1]=1e9;
f[u][0]=0;
f[u][2]=w[u];
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
dfs(j);
f[u][0]+=min(f[j][1],f[j][2]);
f[u][2]+=min({f[j][0],f[j][1],f[j][2]});
}
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
f[u][1]=min(f[u][1],f[u][0]+f[j][2]-min(f[j][1],f[j][2]));
}
}
int main(){
cin>>t;
memset(h,-1,sizeof h);
for(int i=1;i<=t;i++){
int id,val;
cin>>id>>val;
int n;
cin>>n;
w[id]=val;
while(n--){
int x;
cin>>x;
st[x]=true;
}
}
for(int i=1;i<=t;i++){
if(!st[i]){
root=i;
break;
}
}
dfs(root);
cout<<min(f[root][1],f[root][2])<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N=1510;
int idx,e[N],ne[N],h[N];
bool is_root[N];
int root;
int f[N][N];
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u){
f[u][1]=1;
f[u][0]=0;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
dfs(j);
f[u][1]+=min(f[j][0],f[j][1]);
f[u][0]+=f[j][1];
}
}
int main(){
int n;
while(cin>>n){
memset(h,-1,sizeof h),idx=0;
memset(is_root,0,sizeof is_root);
for(int i=1;i<=n;i++){
int a,b,c;
scanf("%d:(%d)",&a,&c);
while(c--){
cin>>b;
is_root[b]=true;
}
}
for(int i=0;i<n;i++){
if(!is_root[i]){
root=i;
break;
}
}
dfs(root);
cout<<min(f[root][0],f[root][1])<<endl;
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
int n,m;
const int N=110,M=N<<1;
int idx,e[M],ne[M],h[N],w[M];
int f[N][N];
void dfs(int u,int fa){
for(int i=h[u];i!=-1;i=ne[i]){
int uu=e[i];
if(uu==fa)continue;
dfs(uu,u);
for(int j=m;j>=0;j--){
for(int k=0;k<=j-1;k++){
f[u][j]=max(f[u][j],f[u][j-1-k]+f[uu][k]+w[i]);
}
}
}
}
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
signed main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n-1;i++){
int a,b,c;
cin>>a>>b>>c;
}
dfs(1,-1);
cout<<f[1][m]<<endl;
return 0;
}


• $Time:23:18$
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int sum[N];
int idx,e[N],ne[N],h[N];
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int res;
int d1[N],d2[N];
void dfs(int u){
if(d1[u])return ;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
dfs(j);
if(d1[j]+1>d1[u]){
d2[u]=d1[u];
d1[u]=d1[j]+1;
}
else if(d1[j]+1>d2[u]){
d2[u]=d1[j]+1;
}
}
res=max(res,d1[u]+d2[u]);
}
int main(){
int n;
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
for(int j=2;j<=n/i;j++){
sum[i*j]+=i;
}
for(int i=2;i<=n;i++){
}
for(int i=1;i<=n;i++){
dfs(i);
}
cout<<res<<endl;
return 0;
}


• $Time:2021/11/13$ $3:03$

$LCA倍增模型$

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=N<<1;
int idx,e[M],ne[M],h[N],w[M];
int d1[N],d2[N],p1[N];
int up[N];
const int INF=0x3f3f3f3f;
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs2(int u,int fa){
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(j==fa)continue;
if(j==p1[u]){
up[j]=max(up[u],d2[u])+w[i];//有路径压缩思想
}
else{
up[j]=max(up[u],d1[u])+w[i];
}
dfs2(j,u);
}
}
int dfs1(int u,int fa){
d1[u]=d2[u]=-INF;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(j==fa)continue;
int d=dfs1(j,u)+w[i];
if(d>d1[u]){
d2[u]=d1[u];
d1[u]=d;
p1[u]=j;
}
else if(d>d2[u]){
d2[u]=d;
}
}
if(d1[u]==-INF){
d1[u]=d2[u]=0;
}
return d1[u];
}
int main(){
int n;
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n-1;i++){
int a,b,c;
cin>>a>>b>>c;