又炸了啊。。。。。。
这次考试时候状态十分不对，上来T2原题，然后又双叒叕看错题肛了1h+，发现看错题之后心态直接崩了
然后开始浑身发冷，去厕所吐了一会感觉好些了，回来看T1
发现是个贪心，然后。。。。。。然后我在脑子不清醒的情况下打了个暴力贪心？！WTF？？！？
后来继续肛T2，发现时间复杂度不对之后整个人又不好了，最后2分钟码了个暴力扔上去
最终得分50+30+0=80pts，rank33
怎么说呢，从到第一机房之后就没考过这么低的分数，也算给自己浇了一盆冷水吧
但不管怎么说，奥赛仍然是我很喜欢的一项事业，我也不打算就这么放弃啊
努力吧。
以上。
T1、Blue
一个很简单的贪心，每个青蛙都尽量往后跳就好了
那么我们可以开一个STL：：set来维护石头，跳过的直接删除，总复杂度O(nlogn)，可以得到AC
然而这种做法其实是没有深入思考的体现
我们继续观察，根据上面贪心的策略，可以发现转移到每个石头的点都是单调的
那么我们岂不是直接维护i一个单调队列就好了？依次扫描每个石头判断队头i是否合法就好了
最后留在队列里的个数就是答案
set
单队
T2、Weed
原题啊。。。。。。考场上毫无头绪也是醉了（yzh学长我对不起你）
直接维护答案肯定不可做，我们考虑分几种来维护（参考山海经）
设cut，has，key分别表示删除的层数，剩下的层数，答案
考虑怎么合并左右区间，分这样几种情况来讨论
1、右儿子能把左儿子删完
has和key直接继承右儿子，cut=cut[ls]+cut[rs]-has[ls];
2、右儿子没有删除操作
直接合并就好了
3、右儿子有删除，但不能把左儿子删完
has直接合并两个儿子，cut直接继承左儿子，key的统计很麻烦，我们这里引入一个函数cal(x,y)，表示在x这棵子树里删除y层剩余答案
现在假设我们已经能够维护出cal，那么显然key=key[rs]+cal(ls,cut[rs])
现在考虑怎么维护cal，显然我们优先考虑右子树，然后根据右树是否删完讨论就好了
总复杂度O(nlog2n)
View Code
T3、Drink
乱搞神仙啊。。。。。。
直接暴力修改单次是n^2肯定过不了，需要找到至多O(n)单次修改的东西
我们发现只有边界上的相互关系会改变，我们考虑只修改边界
使用动态链表，每次把一个方格切下旋转并重连
但是我们发现如果仅仅把边界上的相互关系修改的话，中间点的方向会发生问题，但是修改方向的话又变成n^2了
我们发现一个点的方向可以由相邻点的方向唯一确定，考虑在原网格图中加入不动点
然后中间点的方向可以由不动点推出
这样就可以做到单词O(n)修改，只是常数稍大
#include<bits/stdc++.h>
#define ll long long
#define cri const register int
#define db double
#define re register
#define rf(x) p[x].to[(1+di[x])&3]
#define ff(x) p[x].to[di[x]]
#define bf(x) p[x].to[(2+di[x])&3]
#define lf(x) p[x].to[(3+di[x])&3]
using namespace std;
const int mx[4]={-1,0,1,0},my[4]={0,1,0,-1};
int is[2002][2002];
int cnt,top;
int iss[4010010];
int fro[2002],rig[2002],lef[2002],en[2002];
int sh[2002],xi[2002],zu[2002],yo[2002];
short di[4010010];
int a[4010010];
struct node{
int to[4];
}p[4010010];
inline short its(cri x,cri y)
{
for(int i=0;i<4;i++)
if(p[x].to[i]==y)
return i;
}
inline void get_lf(cri x,cri y)
{
di[y]=(3+its(y,x))&3;
}
inline void get_rf(cri x,cri y)
{
di[y]=(1+its(y,x))&3;
}
inline void get_ff(cri x,cri y)
{
di[y]=(2+its(y,x))&3;
}
inline void get_bf(cri x,cri y)
{
di[y]=its(y,x);
}
int main()
{
int n,m,q,x,y,c;
scanf("%d%d%d",&n,&m,&q);
for(int i=0;i<=m+1;i++) is[0][i]=++cnt;
for(int i=1;i<=n;i++)
{
is[i][0]=++cnt;
for(int j=1;j<=m;j++){
x=getchar();
while(x<'0'||x>'9') x=getchar();
is[i][j]=++cnt,a[cnt]=x-'0';
}
is[i][m+1]=++cnt;
}
for(int i=0;i<=m+1;i++) is[n+1][i]=++cnt;
for(int i=0;i<=n+1;i++)
{
for(int j=0;j<=m+1;j++)
{
for(int k=0;k<4;k++)
if(i+mx[k]>=0&&j+my[k]>=0&&i+mx[k]<=n+1&&j+my[k]<=m+1)
p[is[i][j]].to[k]=is[i+mx[k]][j+my[k]];
}
}
while(q--)
{
scanf("%d%d%d",&x,&y,&c);
int fr=is[x][0];top=0;
for(int i=1;i<=y;i++)
get_rf(fr,rf(fr)),fr=rf(fr);
get_ff(fr,ff(fr)),fro[1]=ff(fr);sh[1]=fr;iss[++top]=fr;
for(int i=2;i<=c;i++)
{
get_rf(fr,rf(fr));
fr=rf(fr);
sh[i]=fr;
get_ff(fr,ff(fr));
fro[i]=ff(fr);
iss[++top]=fr;
}
get_rf(fr,rf(fr)),rig[1]=rf(fr);yo[1]=fr;
for(int i=2;i<=c;i++)
{
get_bf(fr,bf(fr));
fr=bf(fr);
yo[i]=fr;
get_rf(fr,rf(fr));
rig[i]=rf(fr);
iss[++top]=fr;
}
get_bf(fr,bf(fr)),en[1]=bf(fr);xi[1]=fr;
for(int i=2;i<=c;i++)
{
get_lf(fr,lf(fr));
fr=lf(fr);
xi[i]=fr;
get_bf(fr,bf(fr));
en[i]=bf(fr);
iss[++top]=fr;
}
get_lf(fr,lf(fr)),lef[1]=lf(fr);zu[1]=fr;
for(int i=2;i<=c;i++)
{
get_ff(fr,ff(fr));
fr=ff(fr);
zu[i]=fr;
get_lf(fr,lf(fr));
lef[i]=lf(fr);
iss[++top]=fr;
}
for(int i=1;i<=top-1;i++) (di[iss[i]]+=3)&=3;
for(int i=1;i<=c;i++)
{
lf(rig[i])=sh[i];rf(sh[i])=rig[i];
ff(en[i])=yo[i];bf(yo[i])=en[i];
rf(lef[i])=xi[i];lf(xi[i])=lef[i];
bf(fro[i])=zu[i];ff(zu[i])=fro[i];
}
}
for(int i=1;i<=n;i++)
{
int fr=is[i][0];
get_rf(fr,rf(fr));fr=rf(fr);
putchar(a[fr]+'0'),putchar(' ');
for(int j=2;j<=m;j++)
get_rf(fr,rf(fr)),fr=rf(fr),putchar(a[fr]+'0'),putchar(' ');
puts("");
}
}