You are right, but GeenShen is a brand new open world adventure game independently developed by Yohomi. The game takes place in a fantasy world called KunZone, where the person selected by Kun will be awarded KunPower. You will play a mysterious character named AntiIKun. During your free travel, you will meet animal companions with different personalities and unique abilities. Sing, dance, and Rap with them for two years and a half, and find the lost chickens------Meantime, gradually discover the truth about "the most beautiful chicken".
这玩意被 AT 分类到 AGC Class 里边了，不做一下显得不够意思。
chino 老师不喝我的咖啡，理由是晚上了。我的意见：咖啡不是为了好喝才喝吗，正经人谁喝咖啡提神啊。
但是牛子老师喝了咖啡很困。我喝了咖啡也很困。导致今天晚上说话都比较精神状态（现在似乎应该是昨天了）。
CODEFESTIVAL 2016
你说的对。但是入门也要做难题也要做才健全。啊我只会入门啊那没事了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <iostream>
using namespace std;
char s[15];
int main(){
scanf("%s",s+1);
for(int i=1;i<=4;i++)putchar(s[i]);putchar(' ');
for(int i=5;i<=12;i++)putchar(s[i]);puts("");
return 0;
}
Friendly Rabbits
你说的对。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int n,ans,a[100010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[a[i]]==i)ans++;
}
printf("%d\n",ans);
return 0;
}
Next Letter
nssd。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int n,k;
char s[100010];
int main(){
scanf("%s%d",s+1,&k);n=strlen(s+1);
for(int i=1;i<=n;i++){
int val=('a'-s[i]+26)%26;
if(val<=k)s[i]='a',k-=val;
}
k%=26;
while(k)s[n]=(s[n]+1-'a')%26+'a',k--;
printf("%s\n",s+1);
return 0;
}
Grid and Integers
什么 b gap。昏睡高桥。
洛谷题面排版很 sb，建议看 AT 原题面，不容易漏掉信息。漏掉必须是自然数被创到了，看到题解才发现少看了条件。
首先手模一下可以得到性质：两行的对应相同位置差相等，两列同理。这样可以判掉已经不合法的。然后是看填满了以后是否合法，需要让所有填的数都是自然数。那可以写个带权并查集维护行列差值并找到最小的数，判是不是负数。
那我获得了成就：在所有人都担心的精神状态下写带权并查集然后一个样例一个样例调。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
#define int long long
using namespace std;
int n,m,k;
struct node{
int x,y,val;
}a[100010];
bool cmp1(node a,node b){
return a.x<b.x;
}
bool cmp2(node a,node b){
return a.y<b.y;
}
struct Uni{
int fa[100010],val[100010],mn[100010],mn2[100010];
int find(int x){
if(fa[x]==x)return x;
int rt=find(fa[x]);
val[x]+=val[fa[x]];
return fa[x]=rt;
}
void merge(int x,int y,int w){
w=w-val[x]+val[y];
x=find(x);y=find(y);
fa[x]=fa[y];val[x]=w;
}
bool check(int x,int y,int w){
return val[x]-val[y]==w;
}
}R,C;
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++)R.fa[i]=i,R.mn[i]=R.mn2[i]=0x3f3f3f3f;
for(int i=1;i<=m;i++)C.fa[i]=i,C.mn[i]=C.mn2[i]=0x3f3f3f3f;
for(int i=1;i<=k;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].val);
sort(a+1,a+k+1,cmp1);
for(int i=1;i<k;i++){
if(a[i].x==a[i+1].x){
if(C.find(a[i].y)==C.find(a[i+1].y)){
if(!C.check(a[i].y,a[i+1].y,a[i+1].val-a[i].val)){
puts("No");return 0;
}
}
else C.merge(a[i].y,a[i+1].y,a[i+1].val-a[i].val);
}
}
sort(a+1,a+k+1,cmp2);
for(int i=1;i<k;i++){
if(a[i].y==a[i+1].y){
if(R.find(a[i].x)==R.find(a[i+1].x)){
if(!R.check(a[i].x,a[i+1].x,a[i+1].val-a[i].val)){
puts("No");return 0;
}
}
else R.merge(a[i].x,a[i+1].x,a[i+1].val-a[i].val);
}
}
for(int i=1;i<=k;i++){
int x=R.find(a[i].x);
R.mn[x]=min(R.mn[x],R.val[a[i].x]+a[i].val);
}
for(int i=1;i<=n;i++){
int x=R.find(i);
R.mn2[x]=min(R.mn2[x],-R.val[i]);
}
for(int i=1;i<=n;i++){
if(R.find(i)==i&&R.mn[i]+R.mn2[i]<0){
puts("No");return 0;
}
}
for(int i=1;i<=k;i++){
int x=C.find(a[i].y);
C.mn[x]=min(C.mn[x],C.val[a[i].y]+a[i].val);
}
for(int i=1;i<=m;i++){
int x=C.find(i);
C.mn2[x]=min(C.mn2[x],-C.val[i]);
}
for(int i=1;i<=m;i++){
if(C.find(i)==i&&C.mn[i]+C.mn2[i]<0){
puts("No");return 0;
}
}
puts("Yes");
return 0;
}
LRU Puzzle
被自己菜到了。2700 结论题不会。
首先把原问题转化成：把 \(a\) 分成 \(n\) 个子序列，让每个子序列对一个原始数组操作一遍得到的结果相同。
接下来是整个题目的核心一步：我们把对原始数组的一系列操作 \(a_1\cdots a_L\) 变成如下操作：倒着扫 \(a\)，初始化答案数组 \(f\) 为空，如果 \(a_i\) 没有出现过就在答案数组后边加上 \(a_i\)，否则不管。最后把所有没加过的数从小到大顺序加到 \(f\) 最后。显然这和原操作是等价的。
于是根据这一步，我们可以得到一个性质：设这些子序列分别为 \(a_1,\cdots a_n\)，原序列为 \(a\)，那么考察第一个加入子序列的元素，一定和操作 \(a\) 序列时第一个加入的元素一样。以此类推，可以得到每个子序列操作一遍都和原序列操作一遍得到的结果是相同的。
于是处理出原序列的操作结果 \(f\)，那么仍然倒着扫原序列 \(a\)，考虑把 \(a_i\) 分到哪个子序列中。显然可以贪心地取没有分过 \(a_i\) 且分到之后答案仍然可以是 \(f\) 前缀的子序列。直接做是 \(O(nm)\) 的，但是由于每个答案都是 \(f\) 的一个前缀，可以记录答案扩展到 \(f\) 的每个位置的子序列有多少个，然后 \(O(1)\) 取到能扩展的子序列。最后判断的时候也只需要判答案最短的子序列是否合法。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n,m,q,a[100010],cnt[100010],f[100010],pos[100010];
bool vis[100010];
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=q;i++)scanf("%d",&a[i]);
for(int i=q;i>=1;i--)if(!vis[a[i]])f[++f[0]]=a[i],vis[a[i]]=true;
for(int i=1;i<=m;i++)if(!vis[i])f[++f[0]]=i;
for(int i=1;i<=m;i++)pos[f[i]]=i;
cnt[0]=n;
for(int i=q;i>=1;i--){
int p=pos[a[i]];
if(cnt[p-1])cnt[p-1]--,cnt[p]++;
}
int p;
for(int i=0;i<=q;i++)if(cnt[i]){
p=i;break;
}
for(int i=p+2;i<=m;i++)if(f[i]<f[i-1]){
puts("No");return 0;
}
puts("Yes");
return 0;
}