A.Important Exam
题意
有 $N$ 个人考 $M$ 道题 ，给出每个人每道题的答案，求如何安排每道题的正确答案，使得所有人获得的分数总和最大。
$N,M\le 1000$ 。
题解
真理掌握在大多数人手中。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
char s[1005];
int n,m,cnt[1005][26],v[1005];
signed main()
{
n=read(); m=read();
for (int i=1;i<=n;i++)
{
scanf("%s",s+1);
for (int j=1;j<=m;j++) cnt[j][s[j]-'A']++;
}
for (int i=1;i<=m;i++) v[i]=read();
int ans=0;
for (int i=1;i<=m;i++)
{
int mx=0;
for (int j=0;j<26;j++) mx=max(mx,cnt[i][j]);
ans+=mx*v[i];
}
return !printf("%d",ans);
}B.Zero Array
题意
有一个长度为 $N$ 的序列，每次可以选择两个数 $-1$ ，问能否全部减为 $0$ 。
$N\le 10^5$ 。
题解
如果总和为奇数，显然无解。
然后可以大胆猜想，只要不存在一个数使得其它数加起来都 $<$ 它，那么就是有解的。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int n,s[100005];
signed main()
{
n=read();
long long sum=0;
for (int i=1;i<=n;i++) s[i]=read(),sum+=s[i];
if (sum&1) return 0&puts("NO");
sort(s+1,s+n+1);
if (sum-s[n]<s[n]) return 0&puts("NO");
return 0&puts("YES");
}C.Maximum Median
题意
一个长度为 $N$ 的数列，每次操作可以选择一个数 $+1$ ，一共可以进行 $K$ 次操作。问操作完后中位数最大是多少？
$N\le 200000 \ , \ K\le 10^9$ 。
题解
给中位数之前的数加是没有意义的，所以先排一遍序找到中位数。
接下来的过程可以理解成找到中位数 $m$ 后面的一个数 $x$，把 $[m,x]$ 的所有数都变成 $x$ 。可以枚举找到最大的 $x$ 。
$K$ 可能还能剩下，那么就把 $K$ 平均分给 $[m,x]$ 的每个数。我最开始平均分的 $[m,N]$ WA了无数次。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
ll n,m,k,s[200005];
signed main()
{
n=read(); k=read();
for (ll i=1;i<=n;i++) s[i]=read();
sort(s+1,s+n+1);
m=(n>>1)+1;
ll ans=s[m],lasti=m;
for (int i=m+1;i<=n;i++)
{
if ((s[i]-s[i-1])*(i-m)<=k)
{
k-=(s[i]-s[i-1])*(i-m);
ans=s[i];
lasti=i;
}
else break;
}
return !printf("%lld",ans+k/(lasti-m+1));
}D.Treasure Hunting
题意
有一个$n\times m$的矩阵，行的标号从 $1$ 到 $n$ ，列的标号从 $1$ 到 $m$ ，矩阵中共有 $k$ 个宝藏，第 $i$ 个宝藏的位置为 $(r_i,c_i)$ 。有 $q$ 个安全的列，第 $i$ 个安全的列的编号是 $b_i$ 。
从 $(1,1)$ 出发。可以自由的向左向右走；只有安全列可以向上走；不能向下走。问至少要多少步才能收集所有宝藏。
题解
用 $f[i][0/1]$ 表示到第 $i$ 行，取完所有宝藏后在 左/右边 的最小步数。
可以发现最优情况一定是从离 另一侧 最近的两个安全通道上来（左右两个），所以二分查找一下即可。
注意如果当前行没有宝藏就直接上去，但要继承上一行 $l[i],r[i]$ 的值。初值处理也需要注意。
还有只需要取完宝藏，不一定要走完。所以先得到最大的 $r_i$ ，搜索到那一层即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const ll N=200005;
ll n,m,k,q,x,y,l[N],r[N],s[N],f[N][2];
signed main()
{
memset(l,0x3f,sizeof(l));
n=read(); m=read(); k=read(); q=read();
ll maxX=0;
for (ll i=1;i<=k;i++)
{
x=read(); y=read();
maxX=max(maxX,x);
l[x]=min(l[x],y);
r[x]=max(r[x],y);
}
for (ll i=1;i<=q;i++) s[i]=read();
sort(s+1,s+q+1);
if (r[1])
{
f[1][0]=r[1]*2-1-l[1];
f[1][1]=r[1]-1;
}
else l[1]=r[1]=1;
for (ll i=2;i<=n;i++)
{
if (!r[i])
{
f[i][0]=f[i-1][0]+1;
f[i][1]=f[i-1][1]+1;
l[i]=l[i-1];
r[i]=r[i-1];
continue;
}
ll L=*(upper_bound(s+1,s+q+1,r[i])-1),R=*lower_bound(s+1,s+q+1,r[i]); //右侧最近的通道
f[i][0]=1e18;
if (L)
{
f[i][0]=min(f[i][0],f[i-1][1]+abs(r[i-1]-L)+abs(r[i]-L));
f[i][0]=min(f[i][0],f[i-1][0]+abs(l[i-1]-L)+abs(r[i]-L));
}
if (R)
{
f[i][0]=min(f[i][0],f[i-1][1]+abs(r[i-1]-R)+abs(r[i]-R));
f[i][0]=min(f[i][0],f[i-1][0]+abs(l[i-1]-R)+abs(r[i]-R));
}
f[i][0]+=r[i]-l[i]+1; //还有向上的一步以及从右到左
L=*(upper_bound(s+1,s+q+1,l[i])-1),R=*lower_bound(s+1,s+q+1,l[i]);
f[i][1]=1e18;
if (L)
{
f[i][1]=min(f[i][1],f[i-1][0]+abs(l[i-1]-L)+abs(l[i]-L));
f[i][1]=min(f[i][1],f[i-1][1]+abs(r[i-1]-L)+abs(l[i]-L));
}
if (R)
{
f[i][1]=min(f[i][1],f[i-1][0]+abs(l[i-1]-R)+abs(l[i]-R));
f[i][1]=min(f[i][1],f[i-1][1]+abs(r[i-1]-R)+abs(l[i]-R));
}
f[i][1]+=r[i]-l[i]+1;
}
return !printf("%lld",min(f[maxX][0],f[maxX][1]));
}