（图其实有几处偏差，懒得改了）
题目链接
https://codeforces.com/contest/1173
A. Nauuo and Votes
大意
一条评论，有 \(x\) 人投赞成票，\(y\) 人投反对票，\(z\) 人投的票并不确定，试确定这个评论的得票状况（赞成票多，反对票多，或是两者一样多），或者得出无法唯一确定得票情况。
题解
对不确定投票的 \(z\) 人，贪心地考虑两种极端情况：全部赞成或全部反对。分别计算这两种情况下的得票情况。
如果这两种情况下得票状况相同，则可以确定得票情况，否则不能确定。
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int res1=x-y+z,res2=x-y-z;
if(res1<0)res1=-1;
else if(res1>0)res1=1;
if(res2<0)res2=-1;
else if(res2>0)res2=1;
if(res1!=res2)puts("?");
else if(!res1)puts("0");
else if(res1>0)puts("+");
else puts("-");
return 0;
}
B. Nauuo and Chess
大意
在一个 \(m \times m\) 的棋盘上放 \(n\) 个棋子，棋子 \(i\) 坐标为 \((r_i,c_i)\)，要求满足 \(|r_i-r_j|+|c_i-c_j|\ge|i-j|\)。
试求最小的 \(m\) 和一种构造方案。
题解
一种构造方式是这样的：将前 \(\left\lfloor\frac n 2\right\rfloor+1\) 个棋子按编号顺序从左往右放在第一行，剩下的棋子按编号顺序从上往下放在最后一列。（也就是摆成L形）
事实上，一切满足 \(r_i+c_i=i+1\) 的方案都是可行解。证明可以参考官方题解的思路，这里略去。
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
int r,c;
}a[1005];
int main()
{
int n;
scanf("%d",&n);
a[1].r=a[1].c=1;
int mid=n/2+1;
printf("%d\n",mid);
for(int i=1;i<=mid;i++)
printf("1 %d\n",i);
for(int i=mid+1;i<=n;i++)
printf("%d %d\n",i-mid+1,mid);
return 0;
}
C. Nauuo and Cards
大意
有 \(2n\) 张牌，其中 \(n\) 张牌有编号，且编号恰好为 \(1 \ldots n\)，刚开始时 \(n\) 张牌在手上，剩下 \(n\) 张牌在牌堆里。
每次可以将手上的一张牌放入牌堆底部，再将牌堆顶的牌拿到手中，求至少要几次操作可以让牌堆中的牌从堆顶到堆底恰好排成 \(1 \ldots n\)。
题解
分两种情况考虑：
- 如果不用将牌堆中的每一张牌都抽出牌堆，显然最小操作数为牌堆每张牌上的数字和它的目标位置差值的最大值。
- 否则，牌堆中的每张牌都会被抽出一次，我们需要算出牌堆中的每张牌被抽出花费的时间和每张牌从手牌放到对应位置需要的时间。答案就是每张牌这两部分时间和的最大值。
问题就剩下如何判断当前局面对应哪一种情况。
考虑编号为 \(1\) 的牌，如果它刚开始在手牌里，显然剩下的牌都需要被抽出一次。
否则，我们需要计算在 \(1\) 号牌被抽出前，剩下所有的牌是否都能到达预定位置，且当前牌堆中任意一张牌与 \(1\) 号牌的相对位置差与最终局面的相对位置差是否相等。
如果相对位置差完全相等，或是无需抽出 \(1\) 号牌即可让剩下的牌都能到预定位置，就按第一种情况处理即可。
#include <cstdio>
#include <algorithm>
using namespace std;
int a[200005],b[200005],res1[200005],res2[200005],pos[200005],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
res1[i]=n-i+1;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
res2[b[i]]=i;
pos[b[i]]=i;
}
int flag=1;
for(int i=2;i<=n;i++)
if(res2[1]<=res1[i]+res2[i]&&pos[i]-pos[1]!=i-1)
{
flag=0;
break;
}
if(pos[1]==0)flag=0;
if(!flag)
{
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,res1[i]+res2[i]);
printf("%d\n",ans);
}
else
{
int ans=0;
for(int i=1;i<=n;i++)
if(i>b[i])ans=max(ans,i-b[i]);
printf("%d\n",ans);
}
return 0;
}
D. Nauuo and Circle
大意
在圆上画一个 \(n\) 个点的树，给出其所有边，要求画边时边必须全部是直边，且边与边之间不能相交，求满足要求的节点排列数。
题解
其实是个结论题。
答案为每个节点度数阶乘之积再乘 \(n\)。
（官方题解也给出了一种树形 DP 的解法，当然这两种解法是完全等价的）
#include <iostream>
#include <algorithm>
#define MOD 998244353
using namespace std;
int t[200005];
int main()
{
int n;
cin>>n;
long long ans=n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
t[u]++,t[v]++;
ans=ans*t[u]%MOD*t[v]%MOD;
}
cout<<ans<<endl;
return 0;
}