Educational Codeforces Round 169 (Rated for Div. 2)(ABCDE)

 A. Closest Point

签到

#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
int n,m;
int q[N];
void solve()
{cin>>n;_rep(i,1,n)cin>>q[i];if(n!=2)cout<<"NO\n";else if(abs(q[1]-q[2])!=1)cout<<"YES\n";else cout<<"NO\n";return ;
}

B. Game with Doors

题意:已知房间和房间初始之间没有门,加门之后房间和房间之间就相互不连通,给定两个区间[l,r],[L,R],问至少加多少扇门可以使得区间各自选一个点,这两个点一定不连通

手玩几个例子就可以发现

给定的区间没有交集的时候用一个门隔断即可

有交集的话交集(假设大小为x)内部的门一定要选上也就是x-1

然后就是边界,假设左端点不同那么左端点靠右的左边还要额外加一扇门,右端点同理

void solve()
{int a,b,c,d;cin>>a>>b>>c>>d;int x=max(a,c),y=min(b,d);if(a==c&&b==d)cout<<b-a<<'\n';else if(x>y)cout<<"1\n";else {int res=0;if(a!=c)res++;if(b!=d)res++;cout<<y-x+res<<'\n';}return ;
}

C. Splitting Items

A,B玩家玩游戏,n个物品都有成本,从A开始轮流拿,假设A一共拿的成本为a,B一共拿的成本为b,那么A要使a-b最大化,B要使a-b最小化,现在B可以加k个成本(k可以分配给任意物品),问最终a-b最小值

思路:假设B不能加成本,A,B显然每次都拿最大值,那么从大到小排序,(编号从1开始比)A拿奇数位,B拿偶数位即可,现在B可以偷偷加成本,那么显然肯定是贪心的拿每个偶数位加成本,但是不能超过前一个奇数位,因为超过的话这一位排序之后就比前一个大了所以排在前一个前面,所以这一位反而变成了奇数位,所以最终偶数位加成本不超过前一个奇数位即可

代码实现:

#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
int n,m,k;
int q[N];
void solve()
{cin>>n>>k;_rep(i,1,n)cin>>q[i];sort(q+1,q+1+n,greater<>());int a=0,b=0;for(int i=1;i<=n;i+=2){a+=q[i];if(i+1<=n){b+=q[i+1]+min(q[i]-q[i+1],k);k-=min(q[i]-q[i+1],k);}}cout<<a-b<<"\n";return ;
}

D. Colored Portals

题意:每一个点对应两个字母,然后点与点之间如果有一个字母相同则可以连一条无向边,权重为两个点下标之差,给定n个点,m次询问,每次询问两个点的下标,要求找到两个点之间的最短路,如果没有则输出-1

思路:一共只有四个字母,可以发现询问的时候只要两个点有一个相同字母,则最短路肯定是两个点直接连边,否则要找一个中转站,两点通过中转站连接,这个中转站显然只要满同不等于a点的两个字母和b点对应的两个字母,其实也相当于这个中转站的字母组成就是a点两个字母取一个,b点两个字母取一个,那就一定能满足题目连边的条件起到中转的目的,为了实现路径最短,显然要在a点左边和右边分别找到第一个中转站或者在b点左边和b点右边找一个中转站,假设坐标为x,那么最短路长度就是abs(b-x)+abs(a-x),实际上最麻烦的点在于:假设要找"BG" 如何找到当前坐标前面第一个"BG”和后面第一个"BG"，那么把所有6种字母组合从1~6编号,然后求pre数组和next数组的时候遍历6个编号即可,具体实现在下面代码里体现

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int qian[7][N];
string s[N];
int id[255];
int get(char a,char b)//编号
{if(id[a]>id[b])swap(a,b);if(id[a]==1)return id[b]-1;else if(id[a]==2)return id[b]+1;else return 6ll;
}
void init()
{id['B']=1;id['G']=2;id['R']=3;id['Y']=4;
}
int pre[N][10],ne[N][10];//pre[i][j]表示i位置第j个字符串的编号(假设为"BG")的前面第一个"BG"的位置
void solve()
{cin>>n>>m;_rep(i,1,n)cin>>s[i];int now[10];_rep(i,1,6)now[i]=0;_rep(i,1,n){	_rep(k,1,6)pre[i][k]=now[k];now[get(s[i][0],s[i][1])]=i;}_rep(i,1,6)now[i]=n+1;_pre(i,n,1){_rep(k,1,6)ne[i][k]=now[k];now[get(s[i][0],s[i][1])]=i;}while(m--){int a,b;cin>>a>>b;if(a>b)swap(a,b);int res=INF;for(auto i:s[a])for(auto j:s[b]){if(i==j)res=b-a;else{int now=get(i,j);if(pre[a][now])res=min(res,abs(a-pre[a][now])+abs(b-pre[a][now]));if(pre[b][now])res=min(res,abs(a-pre[b][now])+abs(b-pre[b][now]));if(ne[b][now]!=n+1)res=min(res,abs(a-ne[b][now])+abs(b-ne[b][now]));
//					if(ne[a][now]!=n+1)//这里没必要了因为如果中转点在中间的话那么答案就是b-a,那么前面的pre[b][now]显然可以遍历到
//						res=min(res,abs(a-ne[a][now])+abs(b-ne[a][now]));}}if(res==INF)cout<<"-1\n";else cout<<res<<'\n';}return ;
}
signed main()
{IOS;init();int T=1;cin>>T;while(T--)solve();return 0;
}

E. Not a Nim Problem

题意,Alice和Bob做游戏,一共给定n堆石子,A先开始,每次可以从一堆石子(假设为y)中拿掉一部分(假设为x),那么一定要保证gcd(x,y)=1,最后轮到谁没有石子了谁就输了,对方就赢了

显然要用到NIM游戏的结论，所以现在要求的就是输入规模1~1e7的每一个数字的sg值

首先看一下一堆石子假设为x,那么x能走到哪些点？

首先x在满足gcd(x,y)==1的时候拿掉y个石子的所有情况构成了一个集合,可以发现和拿掉之后剩余石子x-y构成的集合一定是一样的,因为剩余的石子x-y一定也满足gcd(x,x-y)==1,为什么？假设gcd(x,x-y)=z那么x和y一定都是z的倍数(假设x=a*z,y=b*z,a>b并且gcd(a,b)=1),那么x-y=(a-b)*z,显然可以发现gcd(x,x-y)=z(因为a,b是互质所以a,a-b也互质,PS:假设a,a-b不互质那么a,a-(a-b);也就是a.b不互质与a,b互质矛盾,所以a,a-b必定互质))

现在就可以画图找规律了

手玩以下可以发现（黑色点为石子数量,红色为sg值）

1.sg[1]=0

2.石子数量为偶数时候走不到任何sg值为0的点,所以sg[偶数]=0

举个例子,现在当前只知道sg[0~5]，发现sg[2]=sg[4]=0,sg[0]就不管了因为只有1能走到0,那么我现在要求sg[6],要使得6走到sg值为0的点那就只能走到2,4但是两个偶数的gcd肯定不会为1

3.sg[质数]=质数在质数序列中的编号,比如sg[3]=2,sg[5]=3,可以发现sg[x]能走到的最大sg值是sg[x‘

]，x'为这个质数的上一个质数,所以sg[x]=sg[x']+1

4.对于其他的x,sg[x]=sg[x''],其中x''为x的最小质因数

看上面的图中的9,他的最小质因数是3,首先这个9至少能达到sg[3]-1(也就是sg[9]=sg[3]),因为3是它的质因数,所以它同样可以走到相对于3的所有能走到的点。

然后看一下9能否走到sg[3]?(为什么突然要看这个点呢,因为图中的9走不到sg[3]所以看一下这种情况是不是必然的)看一下sg[3]为什么为sg[3],是因为3这个数可以走到0,1这两个状态(注意是状态(sg值)而不是石子数量)而走不到2这个状态,还有哪些数能满足这个性质？很显然可以发现只要以3为质因数的数字都满足这个性质,回到这一段开始的问题，可以发现要走到sg[3]一定要走到以3为质因数的数字,但是9不可能走到3为质因数的数字因为9和这个数字都是3的倍数,不满足题目要求，所以说9可以走到的状态一定断在了sg[3],那么就可以得到sg[9]=sg[3]

代码实现

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e7+10,INF=4e18;
int n,m;
int prime[N],cnt,sg[N],minprime[N];
bool st[N];
void init()
{for(int i=2;i<N;i++){if(!st[i])prime[cnt++]=i;for(int j=0;prime[j]*i<N;j++){st[prime[j]*i]=true;minprime[prime[j]*i]=prime[j];if(i%prime[j]==0)break;}}for(int i=0;i<cnt;i++)sg[prime[i]]=i+1;return;
}
void solve()
{cin>>n;int res=0;while(n--){cin>>m;if(m%2==0)m=2;else if(st[m])m=minprime[m];res^=sg[m];}if(res)cout<<"Alice\n";else cout<<"Bob\n";return ;
}
signed main()
{IOS;int T=1;cin>>T;init();sg[1]=1;sg[2]=0;while(T--)solve();return 0;
}