CF1447A Add Candies
可以将操作看做将 \(a_i\) 减 \(i\)，然后第 \(i\) 次操作 \(i\) 就是合法的。
#include<iostream>
#include<cstdio>
using namespace std;
int T;
int n;
void solve()
{
scanf("%d",&n);
printf("%d\n",n);
for(int i=1;i<=n;i++)
printf("%d ",i);
printf("\n");
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1447B Numbers Box
令 \(cnt\) 表示负数的个数。如果 \(cnt\) 为偶数则将所有负数当做正数加上；如果 \(cnt\) 为奇数将保留一个最大的负数，剩下的当做正数加上即可。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=15;
int T;
int n,m;
int a[N][N];
void solve()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
int cnt=0;
long long sum=0;
vector<int>val;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]<=0) val.emplace_back(a[i][j]),sum+=-a[i][j],cnt++;
else val.emplace_back(-a[i][j]),sum+=a[i][j];
sort(val.begin(),val.end(),greater<int>());
if(cnt&1) sum+=2*val.front();
printf("%lld\n",sum);
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1447C Knapsack
将物品按照大小从大到小排序，如果能填就尽量填，直到合法为止即可，如果到最后都没有合法表示无解。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200005;
int T;
int n;
long long W;
pair<int,int>a[N];
void solve()
{
scanf("%d%lld",&n,&W);
for(int i=1;i<=n;i++)
{
int w;
scanf("%d",&w);
a[i]={w,i};
}
sort(a+1,a+n+1,greater<pair<int,int>>());
vector<int>pos;
long long sum=0;
for(int i=1;i<=n;i++)
if(sum+a[i].first<=W)
{
sum+=a[i].first;
pos.emplace_back(a[i].second);
if((W+1)/2<=sum)
{
int k=pos.size();
printf("%d\n",k);
for(int u:pos)
printf("%d ",u);
printf("\n");
return;
}
}
printf("-1\n");
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1447D Catching Cheaters
令 \(f_{i,j}\) 表示考虑 \(A\) 的前 \(i\) 个，\(B\) 的前 \(j\) 个的最大答案。如果 \(a_i=b_j\) 将这两个位置加入 \(B,C\) 有 \(2\) 的贡献。直接转移就好了。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=5005;
int n,m;
char s[N],t[N];
int dp[N][N];
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",s+1);
scanf("%s",t+1);
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
dp[i][j]=max(dp[i][j],max(dp[i-1][j]-1,dp[i][j-1]-1));
if(s[i]==t[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+2);
ans=max(ans,dp[i][j]);
}
printf("%d",ans);
return 0;
}
CF1447E Xor Tree
将每个位置插入字典树，对于一个节点，它的两个儿子的连边肯定是各自连边，除非有某个儿子子树内只有一个点。我们相当于要找到一条到根路径使得路径上的点要么只有一个儿子，要么一个儿子的点数为 \(1\)，直接 DFS 处理。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n;
int a[N];
struct Trie
{
int ch[N*31][2];
int tot=1;
void insert(int s)
{
int u=1;
for(int i=30;i>=0;i--)
{
int c=(s>>i)&1;
if(!ch[u][c]) ch[u][c]=++tot;
u=ch[u][c];
}
return;
}
int dfs(int u,int sum)
{
if(!ch[u][0]&&!ch[u][1]) return sum+1;
int res=0;
if(ch[u][0]) res=max(res,dfs(ch[u][0],sum+(ch[u][1]>0)));
if(ch[u][1]) res=max(res,dfs(ch[u][1],sum+(ch[u][0]>0)));
return res;
}
}T;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
T.insert(a[i]);
printf("%d",n-T.dfs(1,0));
return 0;
}
CF1447F Frequency Problem
写了个乱搞。
考虑 \(a_i\leq 100\)。
可以发现，原序列的众数一定为最优序列的众数，考虑枚举另一个众数。
可以将原序列的众数的位置看做 \(+1\)，当前枚举的数看做 \(-1\)，我们相当于要找一个最长的区间使得区间和为 \(0\)。从左往右扫一遍，记录一下每种前缀和的最左端点在哪里算一算。
时间复杂度 \(O(\max(a_i)n)\)。
然后对于 \(a_i\leq n\) 的情况，可以发现瓶颈在于枚举 \(a_i\) 那部分。我们可以将出现次数最多的 \(200\) 个 \(a_i\) 拿出来做一下，然后再随机 \(2000\) 个 \(a_i\) 做一下应该就可以过了。
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<random>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200005;
int n;
int mx;
int a[N];
int cnt[N];
int b[N];
int pre[N*2];
unsigned rand(unsigned l,unsigned r)
{
static mt19937 myrand(time(NULL));
return myrand()%(r-l+1)+l;
}
bool book[N];
int solve(int x)
{
memset(pre,-1,sizeof(pre));
for(int i=1;i<=n;i++)
if(a[i]==mx) b[i]=1;
else if(a[i]==x) b[i]=-1;
else b[i]=0;
for(int i=1;i<=n;i++)
b[i]+=b[i-1];
int res=0;
pre[n]=0;
for(int i=1;i<=n;i++)
if(pre[b[i]+n]==-1) pre[b[i]+n]=i;
else res=max(res,i-pre[b[i]+n]);
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
cnt[a[i]]++;
mx=max_element(cnt+1,cnt+n+1)-cnt;
vector<int>pos;
for(int i=1;i<=n;i++)
if(cnt[i]) pos.emplace_back(i);
sort(pos.begin(),pos.end(),[=](const int &x,const int &y){return cnt[x]>cnt[y];});
int k=pos.size();
int ans=0;
int cnt=0;
for(int j=0;j<min(200,k);j++)
{
int x=pos[j];
book[j]=true;
cnt++;
if(x==mx) continue;
ans=max(ans,solve(x));
}
for(int j=1;j<=min(2000,k)-cnt;j++)
{
int y=rand(0,k-1);
while(book[y]) y=rand(0,k-1);
int x=pos[y];
book[y]=true;
if(x==mx) continue;
ans=max(ans,solve(x));
}
printf("%d",ans);
return 0;
}