比赛地址：http://codeforces.com/contest/812
A. Sagheer and Crossroads
题目的意思是给出4个路口的车辆和人的红路灯状态，判断是否可能车撞人。
关键是题意，然后模拟，注意细节。
#include <bits/stdc++.h>
using namespace std;
int l[5], s[5], r[5], p[5];
int main()
{
for(int i=1; i<=4; i++){
scanf("%d %d %d %d", &l[i],&s[i],&r[i],&p[i]);
}
if(p[1]==1){
if(l[1] || s[1] || r[1] || l[2] || s[3] || r[4]){
puts("YES");
return 0;
}
}
if(p[2]==1){
if(l[2] || s[2] || r[2] || r[1] || l[3] || s[4]){
puts("YES");
return 0;
}
}
if(p[3]==1){
if(l[3] || s[3] || r[3] || l[4] || s[1] || r[2]){
puts("YES");
return 0;
}
}
if(p[4]==1){
if(l[4] || s[4] || r[4] || l[1] || r[3] || s[2]){
puts("YES");
return 0;
}
}
puts("NO");
return 0;
}B. Sagheer, the Hausmeister
题意：n<15,m<=100的矩阵 1为亮,0为灭 每层第一个和最后一个位置为楼梯,每层必须灭完才能到上一层,问全部灯灭完 最小时间?
解法：到上一层只能从左端或者右端走 设dp[i][0/1] : 灭了前i层的灯 &&当前在第i层左/右端时的最小时间。
#include <bits/stdc++.h>
using namespace std;
int n, m, ans=0, l[300], r[300], dp[300][2];
char s[300];
int main()
{
scanf("%d%d",&n,&m);
m+=2;
int maxx=n+1;
for(int i=1; i<=n; i++){
l[i]=1e5,r[i]=0;
scanf("%s",s+1);
for(int j=1; j<=m; j++){
if(s[j]=='1'){
l[i]=min(l[i],j);
r[i]=max(r[i],j);
maxx=min(i,maxx);
}
}
if(l[i]==1e5){
l[i]=1,r[i]=m;
}
}
for(int i=n; i>=maxx; i--){
if(r[i]==m){
if(i==n) dp[i][0]=0,dp[i][1]=m-1;
else{
dp[i][0]=dp[i+1][0]+1;
dp[i][1]=dp[i+1][1]+1;
}
continue;
}
if(i==maxx){
ans=min(dp[i+1][0]+1+r[i]-1,dp[i+1][1]+1+(m-l[i]));
break;
}
if(i==n){
dp[i][0]=2*(r[i]-1);
dp[i][1]=m-1;
continue;
}
dp[i][0]=min(dp[i+1][0]+1+2*(r[i]-1),dp[i+1][1]+m-1+1);
dp[i][1]=min(dp[i+1][1]+(m-l[i])*2+1,dp[i+1][0]+m-1+1);
}
if(maxx==n) ans=r[n]-1;
cout<<ans<<endl;
}C. Sagheer and Nubian Market
排序+二分水题。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL S,a[100010], b[100010];
LL check(int mid){
for(int i=1; i<=n; i++) b[i]=a[i]+1LL*i*mid;
sort(b+1,b+n+1);
LL res=0;
for(int i=1; i<=mid; i++){
res+=b[i];
}
return res;
}
int main(){
cin>>n>>S;
for(int i=1; i<=n; i++){
scanf("%lld",&a[i]);
}
int ans=1;
int l=0,r=n;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)<=S) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d %lld\n", ans,check(ans));
}D. Sagheer and Kindergarten
题意： 一共n个人，m个玩具，然后读入是x和y，表示x要玩y。然后在玩y的人玩的时间不知道（当他得到了所有想要的玩具之后就开始玩，玩完之后将玩具还回），如果x要玩y……..这样形成了一个环，这个环上所有人都会哭。比如1要玩2在玩的玩具，2要玩3的，3要玩1的，就形成了个环，就全都哭了。然后前面k个操作，保证没人哭，后面q个操作，问如果有这个操作，有多少个人哭了
解法：每个人最多只会等1个人玩某个玩具，从某个人出发连一条指向等的人的有向边。最终形成了一个有许多有根树的森林。每个结点最多1个出度，用欧拉路的方式给每个结点的出入标id，就方便判断某两点是否之前在一棵树上，以及在树的路径中经过的结点个数。这样每次询问，如果最后一个玩y的人在以x为根节点的子树上，连接这两个人就形成了一个环，输出这棵子树上结点个数即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n, m, k, q, dfsclk, fa[maxn], pre[maxn], in[maxn], out[maxn];
vector <int> G[maxn];
void dfs(int u){
in[u] = ++dfsclk;
for(int i=0; i<G[u].size(); i++){
dfs(G[u][i]);
}
out[u] = dfsclk;
}
int main()
{
while(~scanf("%d %d %d %d" , &n,&m,&k,&q))
{
for(int i=0; i<maxn; i++) G[i].clear();
memset(fa, 0, sizeof(fa));
memset(pre, 0, sizeof(pre));
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
dfsclk = 0;
for(int i=1; i<=k; i++){
int x,y;
scanf("%d%d",&x,&y);
if(pre[y]) fa[x] = pre[y];//如果有人在x前一个玩y,x得等到前一个玩y的结束
pre[y] = x;
}
for(int i=1; i<=n; i++) G[fa[i]].push_back(i);
for(int i=1; i<=n; i++){
if(!in[i]) dfs(i);
}
while(q--){
int x, y;
scanf("%d %d", &x, &y);
y = pre[y]; //最后一个玩y的人
if(in[x]<=in[y]&&out[x]>=in[y]){
printf("%d\n", out[x]-in[x]+1);
}
else{
printf("0\n");
}
}
}
return 0;
}
E. Sagheer and Apple Tree
题意：有一颗很奇怪的苹果树，这个苹果树所有叶子节点的深度要不全是奇数，要不全是偶数，并且包括根在内的所有节点上都有若干个苹果，现有两个极其聪明的人又来无聊的游戏了，每个人可以吃掉某个叶子节点上的部分苹果（不能不吃），或者将某个非叶子结点上的部分苹果移向它的孩子（当然也不能不移），吃掉树上最后一个苹果的人获胜，问先手是否必胜？不，不是问这个，因为后手可以作弊，他可以交换任意两个节点的苹果数量，问有多少种不同的作弊（交换）方式可以使得后手必胜（不能不交换）？
解法：书上的Nim游戏。
中文版是这位同学写的，尊重版权从我做起。点这里
不如考虑什么时候先手必胜，在尼姆博弈中，将所有的苹果个数依次异或，如果最后答案为0就先手必败，否则必胜，那么树上的呢？其实一样，不妨把节点按照深度分成两种：①想要移动到任意叶子结点都需要偶数步数（深度和最深的叶子结点深度奇偶性相同）；②想要移动到任意叶子结点都需要奇数步数
对于①，玩家只要移动x个苹果到它孩子节点上，那么这x个苹果就一定会变成状态②之下
对于②，玩家只要移动x个苹果到它孩子节点上，那么这x个苹果就一定会变成状态①之下
而孩子结点属于状态①，所以当前玩家只要移动状态②下的x个苹果，那么另一个玩家只要照搬你的移动，将这x个苹果再次移动到当前的孩子，就又变成状态②了，若当前已经到叶子节点无法移动了，另一个玩家就可以直接将这x个苹果吃掉（你就GG，这几个苹果就和没有一样！）
这样就很明显了，先手对于状态②下的苹果，无论怎么移动，最后一定都会被聪明的后手玩家用上述方法吃掉，所以状态②的苹果毫无意义，那么状态①的呢，只要移动一部就会变得状态②从而毫无意义（和没有一样），那这不就转化成了裸的尼姆博弈了么？
结论：只要将所有状态①下的苹果数量异或，最后结果ans若为0则先手必败，否则必胜！
那么怎么解决这道题，其实已经好办了，先判断一波先手必胜还必败。
如果已经必败了，那么后手作弊交换节点时就要尽量避免改变战局，要知道a^b==b^a，异或是满***换律的，所以B可以将所以状态①中任意两个节点互换，或者将状态②中任意两个节点互换，或者将分别属于状态①和状态②中但数量相同的两堆互换，三种情况个数加在一起即是答案。
如果先手必胜，那么后手的交换一定要改变战局，这个时候必须将状态①中的某个节点和状态②中的某个节点互换，那么怎么换呢？亦或性质a^b^b==a，假设当前异或结果是ans，那么只要遍历一遍状态①中的所有节点，对于当前节点的苹果个数temp，在状态②中找到苹果个数为ans^temp的节点，交换即可！最后统计一遍个数便是答案
这题关键是思维，代码就简单了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
typedef long long LL;
struct edge{
int to, next;
}E[maxn*2];
int head[maxn], edgecnt;
void init(){
edgecnt = 0;
memset(head,-1, sizeof(head));
}
void add(int u, int v){
E[edgecnt].to = v, E[edgecnt].next = head[u], head[u] = edgecnt++;
}
map <LL, LL> mp1,mp2;
int dep[maxn];
LL a[maxn], mxdep;
vector <LL> v;
void dfs(int u, int fa, int d){
dep[u] = d;
mxdep = max(mxdep, 1LL*d);
for(int i=head[u]; ~i; i=E[i].next){
int v = E[i].to;
if(v!=fa){
dfs(v,u,d+1);
}
}
}
int main()
{
int n;
while(~scanf("%d", &n)){
v.clear();
mp1.clear();
mp2.clear();
for(int i=1; i<=n; i++) scanf("%lld", &a[i]), v.push_back(a[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(),v.end()),v.end());
init();
for(int i=2; i<=n; i++){
int x;
scanf("%d", &x);
add(x, i);
add(i, x);
}
mxdep = -1;
dfs(1,-1,1);
LL ans = 0, cnt1 = 0, cnt2 = 0;
for(int i=1; i<=n; i++){
if(mxdep%2==dep[i]%2){
mp1[a[i]]++;
ans ^= a[i];
cnt1++;
}
else{
mp2[a[i]]++;
cnt2++;
}
}
if(ans == 0){
ans = cnt1*(cnt1-1)/2+cnt2*(cnt2-1)/2;
for(int i=0; i<v.size(); i++){
ans += mp1[v[i]]*mp2[v[i]];
}
printf("%lld\n", ans);
}
else{
LL temp = ans;
ans = 0;
for(int i=1; i<=n; i++){
if(mxdep%2==dep[i]%2){
ans += mp2[temp^a[i]];
}
}
printf("%lld\n", ans);
}
}
return 0;
}总结：这次比赛的思维能力要求的很高，但是代码写起来很短。所以思维是首先要考虑的。
京公网安备 11010502036488号