本来预计今天考试喜提两个流汗黄豆（不知道流汗黄豆代表什么可以找 emojiforces 插件）的，然而只有一个。挂了 \(20\) 分，于是平均分 \(-20\)。那似乎也是平均分 \(-100\)。那似乎也可以是平均分 \(-150\)。说着题质量不好评价，假归假，菜的真实。
愚者之夜（Ynoi TEST_86，lxl 要拿钱的所以不公开）狗都不改。
不做 AGC 了，明天先学广义二项级数和指数级数。
Signboard
对。我是不是入门题通过数主要来源早期 AGC。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const char t[]={"CODEFESTIVAL2016"};
char s[20];
int main(){
scanf("%s",s);
int ans=0;
for(int i=0;i<16;i++)ans+=s[i]!=t[i];
printf("%d\n",ans);
return 0;
}
Qualification simulator
不对，因为 \(<\) 写成 \(\le\)。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n,a,b;
char s[100010];
int main(){
scanf("%d%d%d%s",&n,&a,&b,s+1);
int cnt=0,cntb=0;
for(int i=1;i<=n;i++){
if(s[i]=='a'){
if(cnt<a+b)cnt++,puts("Yes");
else puts("No");
}
if(s[i]=='b'){
if(cnt<a+b&&cntb<b)cnt++,cntb++,puts("Yes");
else puts("No");
}
if(s[i]=='c')puts("No");
}
return 0;
}
Gr-idian MST
我太菜。
考虑最小生成树过程，贪心。然后记一个这次行 / 列选多少边。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n,m,a[100010],b[100010];
long long ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<m;i++)scanf("%d",&b[i]);
sort(a,a+n);sort(b,b+m);
int cnt1=n+1,cnt2=m+1,x=0,y=0;
while(x+y<n+m){
if(a[x]<b[y]){
if(x<n)ans+=1ll*a[x]*cnt2,x++,cnt1--;
else ans+=1ll*b[y]*cnt1,y++,cnt2--;
}
else{
if(y<m)ans+=1ll*b[y]*cnt1,y++,cnt2--;
else ans+=1ll*a[x]*cnt2,x++,cnt1--;
}
}
printf("%lld\n",ans);
return 0;
}
Greedy customers
看懂题面恐怕比做这题更难。感谢牛子老师翻译题面。
题意大体就是让你确定一个最长的序列 \(p\)，使得顺序对 \(p_i\) 执行如下操作：找到 \(a\) 中最前面的 \(\ge p_i\) 的 \(a_j\)，把它变成 \(a_j-p_i\)，最后 \(a\) 需要全正。找到这个长度。
首先显然贪心，先用 \(1\) 价格把第一个消成 \(1\)。然后看后边的，仍然贪心用最少的钱卖给他。设前面消完之后的最大值为 \(mn\)，那么对于一个新的 \(a_i\)，如果正好是 \(mn+1\)，那不能卖给他。否则用 \(mn+1\) 的钱卖光。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int n,a[100010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
long long ans=a[1]-1,val=1;
for(int i=2;i<=n;i++){
if(a[i]==val+1)val++;
else ans+=(a[i]-1)/(val+1);
}
printf("%lld\n",ans);
return 0;
}
Lexicographical disorder
一个暴力做法是建压缩 trie 然后暴力跑。压缩 trie 的树高是 \(\sqrt{|S|}\) 的所以可以暴力，跑的比正解慢两倍多一点。
正解是考虑对 \(|\Sigma|^2\) 种不同的字符大小关系分别计算贡献，然后加起来。我们可以记录一个 \(val_{i,j}\) 表示字符 \(i\) 比字符 \(j\) 大时的贡献，那么对于每个询问我们可以 \(O(|\Sigma|^2)\) 地扫每一对字符累加 \(val\)。\(val\) 的更新是简单的，dfs 时搜一个儿子 \(i\)，那么对于所有兄弟 \(j\)，把当前的 \(val_{i,j}\) 加上 \(j\) 子树的大小。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n,m,num,trie[400010][26],sz[400010],cnt[400010],id[100010];
string s[100010];
void ins(string s,int x){
int p=0;
for(int i=0;i<s.length();i++){
if(!trie[p][s[i]-'a'])trie[p][s[i]-'a']=++num;
p=trie[p][s[i]-'a'];sz[p]++;
}
cnt[p]++;id[x]=p;
}
int sum,ans[100010],tmp[26],val[26][26];
vector<pair<string,int> >q[400010];
void dfs(int x){
sum+=cnt[x];
for(pair<string,int>p:q[x]){
for(int i=0;i<26;i++)tmp[p.first[i]-'a']=i;
ans[p.second]=sum;
for(int i=0;i<26;i++){
for(int j=i+1;j<26;j++){
if(tmp[i]<tmp[j])ans[p.second]+=val[j][i];
else ans[p.second]+=val[i][j];
}
}
}
for(int i=0;i<26;i++){
if(!trie[x][i])continue;
for(int j=0;j<26;j++){
if(i==j)continue;
if(trie[x][j])val[i][j]+=sz[trie[x][j]];
}
dfs(trie[x][i]);
for(int j=0;j<26;j++){
if(i==j)continue;
if(trie[x][j])val[i][j]-=sz[trie[x][j]];
}
}
sum-=cnt[x];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];ins(s[i],i);
}
cin>>m;
for(int i=1;i<=m;i++){
int od;cin>>od>>s[0];
q[id[od]].push_back(make_pair(s[0],i));
}
dfs(0);
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}