链接：http://codeforces.com/contest/1043
A - Elections - [水水水水题]
题意：
我和另一个人竞争选举，共有 $n$ 个人投票，每个人手上有 $k$ 票，必须投给我或者另一个人。
现在已知每个人给另一个人投 $a_i$ 票，也就是说会给我投 $k-a_i$ 票。求最小的整数 $k$，使得我的票数严格大于另一个人。
题解：
暴力枚举 $k$。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int n,a[maxn];
int main()
{
cin>>n;
int mx=,sum=;
for(int i=;i<=n;i++)
scanf("%d",&a[i]), mx=max(a[i],mx), sum+=a[i];
for(int k=mx;;k++)
{
if(sum<n*k-sum)
{
printf("%d\n",k);
break;
}
}
}
B - Lost Array - [简单数学题]
题意：
我手上有一个序列 $x_0,x_1, \cdots, x_{k-1}$。
现在又有一个长度为 $n+1$ 的序列 $a_0,a_1,a_2, \cdots, a_n$，已知这个序列是通过 $a_i = x_{(i-1) \bmod k} + a_{i-1}$ 计算得到，其中 $i \ge 0$ 且 $a_0 = 0$。
现在序列 $x_0,x_1, \cdots, x_{k-1}$ 丢失了，但给你 $a_0,a_1,a_2, \cdots, a_n$，求可能的 $k(1 \le k \le n)$。
题解：
显然从 $a_1$ 到 $a_k$ 是可以用来直接确定 $x_0,x_1, \cdots, x_{k-1}$，而后面的 $a_{k+1} \sim a_n$ 可以用来判定是否矛盾，不矛盾就是可行的 $k$。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+;
int n,a[maxn];
int x[maxn];
inline bool ok(int k)
{
for(int i=;i<=k;i++) x[i-]=a[i]-a[i-];
for(int i=k+;i<=n;i++) {
if(a[i]!=x[(i-)%k]+a[i-]) return ;
}
return ;
}
int main()
{
cin>>n;
a[]=;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
vector<int> ans;
for(int k=;k<=n;k++) {
if(ok(k)) ans.push_back(k);
}
printf("%d\n",ans.size());
for(int i=;i<ans.size();i++) printf("%s%d",i>?" ":"",ans[i]);
}
C - Smallest Word - [简单模拟]
题意：
给出只包含字符 $a,b$ 的字符串 $s$，现在你从长度为 $1$ 到 $|s|$ 依次遍历所有的前缀子串，你可以选择反转这个前缀子串，或者不动。
现在要你输出 $|s|$ 个选择，使得最后的 $s$ 字典序最小。
题解：
从左到右遍历字符串，对于第 $i$ 个字符，始终保持 $1 \sim i-1$ 个字符保持 "$a,a,\cdots,a,b,b,\cdots,b$" 或者 "$b,b,\cdots,b,a,a,\cdots,a$" 这样的样式。
可以使得最后字符串为 "$a,a,\cdots,a,b,b,\cdots,b$"。
AC代码：
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
cin>>s;
char pre=s[];
for(int i=;i<s.size();i++)
{
if(s[i]=='a')
{
if(pre=='b') printf("1 "), pre='a';
else printf("0 ");
}
if(s[i]=='b')
{
if(pre=='a') printf("1 "), pre='b';
else printf("0 ");
}
}
if(pre=='a') printf("1\n");
else printf("0\n");
}
D - Mysterious Crime - [双指针维护]
题意：
给出 $m$ 个 $1 \sim n$ 的排列，求所有公共子串的数目。
题解：
换句话说，就是在第 $1$ 个排列里找，在其他 $2 \sim m$ 个排列里出现的所有公共子串。
不难想到，可以将第 $1$ 个排列分成若干段，每段都是不能在往右延伸的最长公共子串，例如：$(1,2,3,6,4,5)$ 和 $(4,5,6,1,2,3)$，则可以把第 $1$ 个排列分成 $(1,2,3),(6),(4,5)$。
因此用两根指针分别维护这些段的左右端点，每次找到一个长为 $len$ 的段，就产生贡献 $\frac{(len)(len+1)}{2}$。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const int maxm=;
int n,m;
int nxt[maxm][maxn];
int main()
{
cin>>n>>m;
memset(nxt,,sizeof(nxt));
for(int j=;j<=m;j++)
{
for(int i=,now,pre=;i<=n;i++)
{
scanf("%d",&now);
nxt[j][pre]=now;
pre=now;
}
} ll ans=;
int len=;
for(int i=nxt[][],j;i;i=nxt[][i])
{
for(j=;j<=m;j++) {
if(nxt[j][i]!=nxt[][i]) break;
}
if(j>m && nxt[][i]) len++;
else ans+=(ll)len*(len+)/, len=;
}
cout<<ans<<endl;
}
E - Train Hard, Win Easy - (Done)
题意：
现在共有两道题目，有 $n$ 个人，每个人做第一题会得到 $x$ 的罚时，做第二题会得到 $y$ 的罚时。
他们要两两相互组队，组队之后队里的两个人会一人挑一题做（当然是罚时越小越好），他们在这一轮会得到他们队的总罚时分数。
又知道，有 $m$ 个组是不能组的（这两个人不想组一块儿），现在要求每个人最后会得到的分数。
题解：
直接上 $O(n^2)$ 地算是不现实的。考虑做减法，不妨先不管 $m$ 组人不想组队的情况，直接算出每个人和其他所有人组队，最后会得到多少分，再减去 $m$ 组不能组的分数即可。
考虑如何计算第 $i$ 个人，和其他所有人分别组队后得到的分数。先将所有人按 $x_i - y_i$ 排序，这样一来，对于第 $i$ 个人，
其前面的任意一个人 $j$ 都满足 $x_j - y_j \le x_i - y_i \Rightarrow x_j + y_i \le x_i + y_j$；也就是说，第 $i$ 个人和其前面的人组队，他本人必然会做 $y_i$ 这道题。
其后面的任意一个人 $k$ 都满足 $x_i - y_i \le x_k - y_k \Rightarrow x_i + y_k \le x_k + y_i$；也就是说，第 $i$ 个人和其后面的人组队，他本人必然会做 $x_i$ 这道题。
这样一来，我们只要 $O(n)$ 求出 $x_j$ 的前缀和以及 $y_k$ 的后缀和，然后即可 $O(1)$ 得到第 $i$ 个人的总分数。
最后减去那 $m$ 组人不想组队的情况即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=3e5+;
int n,m;
struct P{
int id;
ll x,y;
P(){}
P(int _id,ll _x,ll _y){id=_id, x=_x, y=_y;}
bool operator<(const P& oth) {
return x-y < oth.x-oth.y;
}
}p[maxn];
pii hate[maxn];
ll xpre[maxn],ysuf[maxn];
ll ans[maxn];
int main()
{
cin>>n>>m;
for(int i=,x,y;i<=n;i++) scanf("%d%d",&x,&y), p[i]=P(i,x,y);
for(int i=;i<=m;i++) scanf("%d%d",&hate[i].first,&hate[i].second);
memset(ans,,sizeof(ans));
for(int i=,a,b;i<=m;i++)
{
a=hate[i].first, b=hate[i].second;
ll des=min(p[a].x+p[b].y,p[a].y+p[b].x);
ans[hate[i].first]-=des;
ans[hate[i].second]-=des;
}
sort(p+,p+n+); xpre[]=;
for(int i=;i<=n;i++) xpre[i]=xpre[i-]+p[i].x;
ysuf[n+]=;
for(int i=n;i>=;i--) ysuf[i]=ysuf[i+]+p[i].y; for(int i=;i<=n;i++) {
ans[p[i].id]+=xpre[i-]+(i-)*p[i].y+ysuf[i+]+(n-i)*p[i].x;
}
for(int i=;i<=n;i++) printf("%lld%c",ans[i],i==n?'\n':' ');
}
F - Make It One - [莫比乌斯反演] - (Undone)
题意：
给出 $n(1 \le n \le 3e5)$ 个数字 $a_1 \sim a_n(1 \le a_i \le 3e5)$，要求选取最少的若干个数字，使他们的最大公因数为 $1$。
题解：