来自FallDream的博客，未经允许，请勿转载，谢谢。
有毒的一场div2 找了个1300的小号，结果B题题目看错没交 D题题目剧毒 E题差了10秒钟没交上去。
233
-------
A.Sagheer and Crossroads
有一个十字路口，分别给出每个方向左右转和直行以及行人的红绿灯的状态，求有没有可能有行人会被车撞
大判断。 附上大佬@ACMLCZH的代码
#include <cstdio>
#include <cstring>
int a[][]; inline int read()
{
int n=,f=; char c=getchar();
while (c<'' || c>'') {if(c=='-')f=-; c=getchar();}
while (c>='' && c<='') {n=n*+c-''; c=getchar();}
return n*f;
} int main()
{
register int i,j,x,y;
for (i=;i<;++i)
for (j=;j<;++j) a[i][j]=read();
for (i=;i<;++i)
for (j=;j<;++j) if (a[i][j]&&a[i][]) return *printf("YES");
if (a[][]) if (a[][]||a[][]||a[][]) return *printf("YES");
if (a[][]) if (a[][]||a[][]||a[][]) return *printf("YES");
if (a[][]) if (a[][]||a[][]||a[][]) return *printf("YES");
if (a[][]) if (a[][]||a[][]||a[][]) return *printf("YES");
printf("NO");
}
B Sagheer, the Hausmeister
给定一个宿舍，两边是楼梯，中间是房间，有些房间有灯亮着，你要从1楼向上走，把一层的灯关完之后才能上楼，问把所有的灯关完至少要走多少步。
直接dp,f[i][0/1]表示关完前i层在左/右边的最小步数。
#include<iostream>
#include<cstdio>
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
} int n,m,r[],l[],f[][];
char st[][]; int main()
{
n=read();m=read()+;
for(int i=;i<=n;++i) scanf("%s",st[i]+);
for(int i=;i<=n;++i)
{
for(int j=m;j;--j)
if(st[i][j]=='') {r[i]=j;break;}
for(int j=;j<=m;++j)
if(st[i][j]=='') {l[i]=j;break;}
}
int i=;
for(;i<=n&&!r[i];++i);
if(i>n) return *puts("");
f[i][]=r[i]-,f[i][]=m-l[i];
for(++i;i<=n;++i)
{
if(!r[i]) f[i][]=f[i-][]+,f[i][]=f[i-][]+;
else
{
f[i][]=min(f[i-][]+*(r[i]-)+,f[i-][]+m);
f[i][]=min(f[i-][]+*(m-l[i])+,f[i-][]+m);
}
}
printf("%d\n",min(f[n][],f[n][]+m-));
return ;
}
C. Sagheer and Nubian Market
有n个物品，基础价格是ci,买k个物品的话价格会变成ci+k*i,求最多能买几个
二分答案，然后排序一下就好了
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
int x;char c;
while((c=getchar())<''||c>'');
for(x=c-'';(c=getchar())>=''&&c<='';)x=(x<<)+(x<<)+c-'';
return x;
}
#define MN 100000
int a[MN+];
long long v[MN+];
int main()
{
int n,m,i,j,l,r,mid,ans,c;
n=read();m=read();
for(i=;i<=n;++i)a[i]=read();
for(l=,r=n;l<=r;)
{
mid=l+r>>;
for(i=;i<=n;++i)v[i]=a[i]+1LL*i*mid;
sort(v+,v+n+);
for(i=,j=m;i<=mid;++i)if(j>=v[i])j-=v[i];else break;
if(i>mid)l=mid+,ans=mid,c=m-j;else r=mid-;
}
printf("%d %d",ans,c);
}
D.毒题
好好写题面不好吗？考验读题能力？？？？
E.Sagheer and Apple Tree
给你一棵树，每个点有一些苹果。两个人博弈。
每次选择一种操作
1)选择一个叶子节点，吃掉一些苹果。
2)选择一个非叶子节点，把一些苹果移到它的儿子处。
n<=10^5 满足叶子结点奇偶性相同。
求有多少种方法交换两个点的苹果数量，后手必胜？
发现当与叶子结同奇偶的苹果树塔起来等于0的时候后手必胜。
枚举换哪个，用个桶统计方案数。
然后如果一开始就是0，偶数深度之间随便换，奇数也是。
#include<iostream>
#include<cstdio>
#define MN 100000
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
} int n,head[MN+],s[],s2[],cnt=,a[MN+];
struct edge{int to,next;}e[MN*+]; inline void ins(int f,int t)
{
e[++cnt]=(edge){t,head[f]};head[f]=cnt;
}
int dd,d[MN+];
void Dfs(int x,int fa,int dep)
{
d[x]=dep;
if(dep&) ++s[a[x]];else ++s2[a[x]];
int son=;
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=fa)
++son,Dfs(e[i].to,x,dep+);
if(!son) dd=dep;
} int main()
{
n=read();
for(int i=;i<=n;++i) a[i]=read();
for(int i=;i<=n;++i)
{
int fa=read();
ins(fa,i);ins(i,fa);
}
Dfs(,,);int ans=,num=;
for(int i=;i<=n;++i)
if((d[i]&)==(dd&))
ans^=a[i],++num;
long long aa=;
for(int i=;i<=n;++i)
if((d[i]&)==(dd&))
aa+=(dd&)?s2[a[i]^ans]:s[a[i]^ans];
if(ans==) aa+=1LL*num*(num-)/+1LL*(n-num)*(n-num-)/;
cout<<aa;
return ;
}