C. Manga
题意：有一本书有 \(n\) 卷，你需要从第一卷开始依次看，一旦没有某一卷就停止。在看之前你可以进行若干次操作，每次卖掉任意两卷并买新的任意一卷。问操作结束后最多能看多少卷。
做法 1
注意到拥有的重复的卷都可以没有损失地卖掉，提前记录一下。然后从小到大扫，如果没有这一卷就尝试卖两本并买这一本。卖的两本优先从重复的卷里考虑，然后再贪心从大到小卖。正确性显然，数据结构维护即可。
By KrK
#include <bits/stdc++.h>
using namespace std;
int n;
set <int> S;
int cur;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int a; scanf("%d", &a);
if (S.count(a)) cur++;
else S.insert(a);
}
for (int i = 1; ; i++)
if (!S.count(i)) {
while (cur < 2 && !S.empty() && *S.rbegin() > i) {
auto it = S.end(); it--;
cur++; S.erase(it);
}
if (cur >= 2) {
cur -= 2;
S.insert(i);
} else {
printf("%d\n", i - 1);
return 0;
}
}
return 0;
}
做法 2
考虑二分答案。对于读 \(i\) 卷的情况，将 \(>i+1\) 的卷和 \(\le i\) 的重复的卷全部卖掉替换，判断是否能填补空隙。
By heno239
void solve() {
int n; cin >> n;
vector<int> a(n);
rep(i, n)cin >> a[i];
//[1,x]
auto can = [&](int x) {
vector<int> cnt(x+1);
int z = 0;
rep(i, n) {
if (a[i] > x)z++;
else {
if (cnt[a[i]])z++;
cnt[a[i]] = 1;
}
}
int r = 0;
rep1(i, x) {
if (!cnt[i])r++;
}
if (z >= 2 * r)return true;
return false;
};
int le = 0, ri = n + 5;
while (ri - le > 1) {
int m = (le + ri) / 2;
if (can(m)) {
le = m;
}
else {
ri = m;
}
}
cout << le << "\n";
}
做法 3
与二分答案类似，但将二分改成了枚举。注意到读的卷数一定不会超过 \(n\)，所以 \(>n\) 的卷都可以直接卖掉。考虑统计能否读 \(i\) 卷。考虑设计 \(bak[i]\) 表示 \(\le i\) 的卷有多少种，则如果要读 \(i\) 卷，将会有 \(i-bak[i]\) 个位置空缺。这些位置可以使用多余的补上，而只有 \(bak[i]\) 卷是不多余的（每种只有一卷不多余，剩下的都多余），所以总的多余的数量为 \(n-bak[i]\)，比较空缺位置与多余数量的一半即可。
By He_Ren
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 3e5 + 5;
int a[MAXN], bak[MAXN];
int main(void)
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; ++i)
scanf("%d",&a[i]);
for(int i=1; i<=n; ++i)
if(a[i] <= n) bak[a[i]] = 1;
for(int i=1; i<=n+1; ++i)
bak[i] += bak[i-1];
for(int i=1; i<=n+1; ++i)
{
if(i - bak[i] > (n - bak[i]) / 2)
{
printf("%d\n",i-1);
return 0;
}
}
return 0;
}
错解
By daisybunny
#include<bits/stdc++.h>
using namespace std;
int n;
int a[300005];
map<int,int> mp;
int ba;
int ans;
int main()
{
cin>>n;
for(int t=0;t<n;t++)
{
cin>>a[t];
mp[a[t]]++;
}
sort(a,a+n);
for(int t=1;;t++)
{
if(mp[t]==0)
{
if(ba>1)
{
ba-=2;
ans++;
}
else if(n>=1&&t<a[n-1]&&ba==1)
{
mp[a[n-1]]--;n--;ba--;ans++;
}
else if(n>=2&&t<a[n-2])
{
mp[a[n-1]]--;mp[a[n-2]]--;n-=2;ans++;
}
else
break;
}
else
{
ans++;
ba+=mp[t]-1;
mp[t]--;
}
}
cout<<ans;
return 0;
}
一组 hack 数据为
6
1 3 4 4 5 5
此时在算到 2 的空缺时，该代码会优先卖掉两个 5，而最优解应该卖掉多余的一个 4 一个 5。此程序的问题在于，他考虑到了优先卖掉重复的，但只判断了优先卖掉 \(\le i\) 的重复的，而没有优先处理 \(>i\) 的重复。
D. Flip and Adjust
题意：有 \(n\) 张卡片，第 \(i\) 张正面为 \(a_i\)，反面为 \(b_i\)，问是否存在一种翻转方案使得卡片的和为 \(S\)。如果有，输出方案。
设 \(dp[i][j]=0/1\) 表示前 \(i\) 张卡片能否得到 \(j\)，则
\[dp[i][j]=dp[i-1][j-a_i] \text{ or } dp[i-1][j-b_i] \]#include<bits/stdc++.h>
using namespace std;
int a[110],b[110];
bool f[110][10010],pre[110][10010];
void get(int now,int x) {
if(now==0) return;
if(pre[now][x])
get(now-1,x-a[now]);
else get(now-1,x-b[now]);
cout<<(pre[now][x]?'H':'T');
}
signed main() {
int n,s;
cin>>n>>s;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=s;j++) {
if(j>=a[i]&&f[i-1][j-a[i]])
f[i][j]=1,pre[i][j]=1;
if(j>=b[i]&&f[i-1][j-b[i]])
f[i][j]=1,pre[i][j]=0;
}
if(f[n][s]) {
cout<<"Yes"<<endl;
get(n,s);
cout<<endl;
}
else cout<<"No"<<endl;
return 0;
}
E. Subsequence Path
题意：有 \(n\) 个点 \(m\) 条有向有权边 \(u_i\xrightarrow{w_i} v_i\) 和一个边的编号序列 \(e_i\)，你可以选择编号序列的一个子序列，使得该子序列的边构成一条 \(1\to n\) 的路径，求最短路径。
直接 DP。令 \(f_{i,j}\) 表示只考虑序列中前 \(j\) 条边，\(1\to j\) 的最短路径，则
\[f_{i,j}=\begin{cases}\min(f_{i-1,j},f_{i-1,u_{e_i}}+w_{e_i})\text{ if }v_{e_i}=j\\f_{i-1,j}\text{ otherwise}\end{cases} \]此时第一维可以省略。转移时只需要更新 \(f_{v_{a_i}}\) 即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct edge {
int u,v,w;
} a[200010];
int e[200010];
int f[200010];
signed main() {
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
cin>>a[i].u>>a[i].v>>a[i].w;
for(int i=1;i<=k;i++)
cin>>e[i];
memset(f,-1,sizeof(f));
f[1]=0;
for(int i=1;i<=k;i++) {
if(f[a[e[i]].u]==-1) continue;
if(f[a[e[i]].v]==-1||f[a[e[i]].v]>f[a[e[i]].u]+a[e[i]].w)
f[a[e[i]].v]=f[a[e[i]].u]+a[e[i]].w;
}
cout<<f[n]<<endl;
return 0;
}
F. XOR on Grid Path
题意：有一个 \(n\times n\) 的矩阵，每个格子有一个正整数，每次只能向右走或向下走，问有多少条路径能从 \((1,1)\) 走到 \((n,n)\)，且路径异或和为 \(0\)。
双向搜索。搜索从 \((1,1)\) 到副对角线的所有方案，存到 \(map\) 里，再搜索从 \((n,n)\) 到副对角线的所有方案，计算答案。
#include<bits/stdc++.h>
using namespace std;
int n,a[30][30];
map<int,int> m[2][21];
void dfs(int x,int y,int f,int flag) {
f^=a[x][y];
if(x+y==n+1) m[flag][x][f]++;
else if(flag) dfs(x-1,y,f,flag),dfs(x,y-1,f,flag);
else dfs(x+1,y,f,flag),dfs(x,y+1,f,flag);
}
signed main() {
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
dfs(1,1,0,0);
dfs(n,n,0,1);
long long ans=0;
for(int i=1;i<=n;i++) {
int x=a[i][n+1-i];
for(auto tmp:m[0][i])
ans+=1ll*tmp.second*m[1][i][tmp.first^x];
}
cout<<ans<<endl;
return 0;
}