经常有人“心血来潮,开了一套AGC”,然后发现各种不会做,“感觉智商被AGC摁在地上摩擦”
今天我们来看一套比较古老的 AGC ,AGC 006
这道题目还是送温暖的...
直接枚举长度从
到
最后的
为用第二个字符串填充,剩余空缺从前到后一次用第一个字符串填充
最后验证前
位是否满足第一个字符串即可
由于是从小到大枚举,枚举到可行直接输出答案即可
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int n,m;
char s[110],t[110],p[210];
bool check(int x)
{
for (int i=1;i<=n;i++)
if (s[i]!=p[i]) return false;
return true;
}
int main()
{
n=read(s),n=strlen(s+1);
m=read(t);int x=0;
for (int i=n;i<=n+n;i++)
{
for (int j=1;j<=i-n;j++)
p[j]=s[j];
for (int j=1;j<=n;j++)
p[(i-n)+j]=t[j];
if (check(i)) {print(i),puts("");return 0;}
}
return 0;
}
这道题目就比较有意思了
首先考虑不可行的情况,显然当
或
的时候是不可行的
因为每一次取的都是三个格子中的中位数,显然到第二行的时候,
或
就消失不见了,更高的行中不可能出现
然后考虑其余情况的构造方法
一种比较通用的构造方法是,最高行为
,我们使得下一行出现至少两个
即可,如下图所示
我们只要保证图中所有的红色格子都是
的话,最后一行一定是
那么,现在,我们只需要构造最后一行的四个格子,使得从第二行开始就在指定位置出现连续的两个
了
这样就比较思博了,
即可
但是我们发现,当
的时候,会有点问题,那么我们对
特判一下,构造
当然,构造的方法不唯一
最后注意特判
的情况,不过我这样构造的话,不会出现问题
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int n,m,a[200010],b[200010];
int main()
{
read(n);read(m);
if (m==1 || m==2*n-1) puts("No");
else
{
puts("Yes");
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
if (m>2)
{
a[n-1]=m-1,a[n]=m,a[n+1]=m+1,a[n+2]=m-2;
b[m-2]=1,b[m-1]=1,b[m]=1,b[m+1]=1;
}
else
{
a[n-1]=m+1,a[n]=m,a[n+1]=m-1,a[n+2]=m+2;
b[m-1]=1,b[m]=1,b[m+1]=1,b[m+2]=1;
}
int x=1;
for (int i=1;i<n-1;i++)
{
while (b[x]==1) x++;
a[i]=x;b[x]=1;
}
for (int i=n+3;i<=2*n-1;i++)
{
while (b[x]==1) x++;
a[i]=x;b[x]=1;
}
for (int i=1;i<=2*n-1;i++)
print(a[i]),puts("");
}
return 0;
}
这道期望题目一颗赛艇啊
首先考虑对称位置的处理,显然
关于
和
的对称位置分别是
和
考虑兔子
的期望
这样,我们似乎已经得到了
的算法
我们从几何角度来考虑一下这个操作
其实就是
相对于
和
的相对位置发生了变化,
在外面的情况也是如此
再一般的来说,就是
和
的值进行了交换
那么,我们考虑差分,这样,每一次的操作就是对两个数进行交换了
而交换操作是分组进行的,我们可以根据类似快速幂的方式,在
的时间内完成交换
那么总的复杂度就是
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int n,m,a[200010],b[200010];
int main()
{
read(n);read(m);
if (m==1 || m==2*n-1) puts("No");
else
{
puts("Yes");
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
if (m>2)
{
a[n-1]=m-1,a[n]=m,a[n+1]=m+1,a[n+2]=m-2;
b[m-2]=1,b[m-1]=1,b[m]=1,b[m+1]=1;
}
else
{
a[n-1]=m+1,a[n]=m,a[n+1]=m-1,a[n+2]=m+2;
b[m-1]=1,b[m]=1,b[m+1]=1,b[m+2]=1;
}
int x=1;
for (int i=1;i<n-1;i++)
{
while (b[x]==1) x++;
a[i]=x;b[x]=1;
}
for (int i=n+3;i<=2*n-1;i++)
{
while (b[x]==1) x++;
a[i]=x;b[x]=1;
}
for (int i=1;i<=2*n-1;i++)
print(a[i]),puts("");
}
return 0;
}
int n,m,a[100010],b[100010],ans[100010],c[100010];
LL K;
double x[100010],z[100010];
void Work(LL x)
{
for (;x;x>>=1)
{
if (x&1)
{
for (int i=1;i<n;i++)
c[i]=ans[b[i]];
for (int i=1;i<n;i++)
ans[i]=c[i];
}
for (int i=1;i<n;i++)
c[i]=b[b[i]];
for (int i=1;i<n;i++)
b[i]=c[i];
}
}
int main()
{
read(n);
int y;
for (int i=1;i<=n;i++)
read(y),x[i]=(double)y;
read(m),read(K);
for (int i=1;i<=m;i++)
read(a[i]);
for (int i=1;i<n;i++)
b[i]=i,ans[i]=i;
for (int i=1;i<=m;i++)
swap(b[a[i]],b[a[i]-1]);
Work(K);
z[1]=x[1];
for (int i=1;i<n;i++)
z[i+1]=z[i]+(x[ans[i]+1]-x[ans[i]]);
for (int i=1;i<=n;i++)
printf("%0.10lf\n",z[i]);
return 0;
}
这道题目似乎是B题的SPJ啊.....
考虑二分答案,假设当前需要验证的答案为
,表示答案
是否成立
那么,根据最下面一行和
的关系,我们可以得到底层的
数列,
表示
我们现在得到了底层的
数列,而题目所给的条件,上一层的一格为
,当且仅当下一层与之对应的三个中至少有两个
现在,符合情况的话,那么就是顶层为
我们可以画画图来分析一下底层的情况,如何向上传导
我们可以发现,当出现连续的两个
的时候,他们所对应的的上面,全部为
那么,这样的情况如何向外拓展呢?
我们发现,当连续的两个
旁边出现隔着一个位置的
的是否,这个全是
的竖行,可以向着隔着一个位置的
的方向拓展一列
那么我们只需要正着反着,各扫一遍
这样一来,我们就可以在
的时间内验证答案了
还有一种比较特殊的情况是,底层不需要出现连续的两个
特判一下
总的时间复杂度是
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=1;
for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0;
for(;(c>='a' && c<='z');s[len++]=c,c=nc());
s[len++]='\0';
return len;
}
inline void read(char &x){
for (x=nc();!(x>='A' && x<='Z');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n,a[200010];
bool check1(int x)
{
for (int i=1;i<2*n;i+=2)
if (a[i]<x) return false;
return true;
}
bool check(int x)
{
if (check1(x)) return true;
int y=0,z;
for (int i=1;i<n;i++)
if (a[i]>=x && a[i+1]>=x) y=i+1;
z=y;
if (z!=0)
{
while (a[z+2]>=x)
{
z+=2,y++;
if (z+2>=2*n) break;
}
if (y>=n) return true;
}
y=0;
for (int i=2*n-1;i>n;i--)
if (a[i]>=x && a[i-1]>=x) y=i-1;
z=y;
if (z!=0)
{
while (a[z-2]>=x)
{
z-=2,y--;
if (z-2<1) break;
}
if (y<=n) return true;
}
return false;
}
int main()
{
read(n);
memset(a,0,sizeof(a));
for (int i=1;i<2*n;i++)
read(a[i]);
int l=2,r=2*n-2,mid,res;
while (l<=r)
{
mid=l+r>>1;
if (check(mid)) l=mid+1,res=mid;else r=mid-1;
}
print(res),puts("");
return 0;
}
这道题目很繁琐啊QAQ......
画了满满一页草稿纸......
首先,我们透过现象看本质,3*3Rotate 实际上就是把左右两列交换,然后在把三列全部倒置
那么,其实可以发现,每一列中的三个数是不会改变的,而且三个数要么正向,要么逆向
再其次,因为交换的是间隔的两列,所以矩阵中的奇数列和偶数列其实是相对独立的
我们把操作分成两个来思考
对间隔的两列旋转(这个旋转操作自带一个倒置和一个左右交换)、对某一列倒置
对于第一个问题的数量,我们可以转为这个问题:给出
个数的一个全排列,每次可以交换相邻的两个数,求每个数被交换的次数
贪心的做,我们先把在最后的数换下去,然后在换倒数第二个.......
暴力的做是
,考虑用树状数组维护一波,
第二个问题,只要判断第一个问题的奇偶性,就可以直接得到答案了
那么回到原问题,可行性怎么判断
首先判断前面提到的一些条件...balabala
然后,就是对后面两个子问题的判断了
对于奇数列的第一个问题,左右交换的前提是其中间的偶数列进行倒置
那么,也就是说,奇数列的第一个问题的奇偶性应当与偶数列的第二个问题相同;偶数列的判断亦是如此
这样一来,问题就解决了,时间复杂度
,不过题解里给出的复杂度是
,不是很明白他是怎么实现的,可能他的
数组可以线性求吧Orz
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int n,a[100010],b[100010],c[100010],d[100010],e[100010],f[100010];
int sum[100010],g[100010];
void updata(int x,int y)
{
for (;x<=n;x+=x&(-x)) g[x]+=y;
}
int SUM(int x)
{
int res=0;
for (;x;x-=x&(-x)) res+=g[x];
return res;
}
void change(int x,int y)
{
for (;x<=n;x+=x&(-x)) sum[x]+=y;
}
int query(int x)
{
int res=0;
for (;x;x-=x&(-x)) res+=sum[x];
return res;
}
bool check()
{
int x,y,z,t;
for (int i=1;i<=n;i++)
{
x=(a[i]-1)/3;t=x+1;
f[i]=t;
if (i%2!=t%2) return false;
y=x*3+2,z=x*3+3,x=x*3+1;
if (a[i]==x && b[i]==y && c[i]==z) {e[t]=2*n;continue;}
if (a[i]==z && b[i]==y && c[i]==x) {e[t]=2*n+1;continue;}
return false;
}
return true;
}
int main()
{
read(n);
for (int i=1;i<=n;i++)
read(a[i]);
for (int i=1;i<=n;i++)
read(b[i]);
for (int i=1;i<=n;i++)
read(c[i]);
if (!check()) {puts("No");return 0;}
memset(sum,0,sizeof(sum));
memset(g,0,sizeof(g));
for (int i=1;i<=n;i++)
if (i%2==1) change(i,1);
int x;
for (int i=n;i>=1;i--)
if (i%2==1)
{
x=f[i];
d[x]=query(n)-query(x);
d[x]+=SUM(x);
change(x,-1);updata(x,1);
}
memset(sum,0,sizeof(sum));
memset(g,0,sizeof(g));
for (int i=1;i<=n;i++)
if (i%2==0) change(i,1);
for (int i=n;i>=1;i--)
if (i%2==0)
{
x=f[i];
d[x]=query(n)-query(x)+SUM(x);
change(x,-1);updata(x,1);
}
for (int i=1;i<=n;i++)
e[i]=(e[i]-d[i])%2;
int s=0,t=0;
for (int i=1;i<=n;i++)
if (i%2==0) s+=e[i];else t+=d[i];
t/=2;
if (s%2!=t%2) {puts("No");return 0;}
s=0,t=0;
for (int i=1;i<=n;i++)
if (i%2==1) s+=e[i];else t+=d[i];
t/=2;
if (s%2!=t%2) {puts("No");return 0;}
puts("Yes");
return 0;
}
又一次深刻体会到了出题人的强大Orz...
首先,我们可以把这个矩阵问题转变为图论问题
我们把格子
转变为一条有向边
,那么,当
和
存在时,有边
我们可以先来尝试探索一些规律
对于图中的
个点,每个点
都有边连向
,我们尝试更新一波边,发现只有在
和
满足
的时候,
有指向
的边
以此,我们发现这张图和
有关系(出题人是这么说的.......)
于是,我们用三色来对图进行染色,使得相邻的节点不同色
接下来,我们分别讨论三种情况
【1】 染色成功,且图中出现了不同的三种颜色
、
、
那么,我们对于三种不同颜色的边,可以把所有
、
、
都连上
证明:如下图,如果上述情况成立的话,那么,一定至少存在
、
,我们当然可以把
连上,当有新的边
时,我们发现,
也同样可以连上,那么,联通的所有点都是可以两先关的
【2】染色成功,图中出现的颜色不足三种
那么显然,不存在
、
这样的边对,那么,答案就是边数
【3】染色失败
那么,画画图很容易看出,一定存在着环(且环的大小一定不是
的倍数)
那么,很显然得,所有联通的点之间,两两之间的所有边均可以连上
这样一来,我们对于每一个联通块一次这样讨论即可,时间复杂度
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int n,m,f[100010];
LL A,B,C,S;
struct data
{
int x,y;
}a[100010];
vector<int> b[100010],c[100010];
bool v[100010];
bool check(int x)
{
v[x]=1;bool flag=1;S+=b[x].size()+c[x].size();
if (f[x]==1)
{
for (int i=0;i<b[x].size();i++)
if (f[b[x][i]]==0) f[b[x][i]]=2,B++;
else if (f[b[x][i]]!=2) flag&=0;
for (int i=0;i<c[x].size();i++)
if (f[c[x][i]]==0) f[c[x][i]]=3,C++;
else if (f[c[x][i]]!=3) flag&=0;
for (int i=0;i<b[x].size();i++)
if (!v[b[x][i]]) flag&=check(b[x][i]);
for (int i=0;i<c[x].size();i++)
if (!v[c[x][i]]) flag&=check(c[x][i]);
}
else if (f[x]==2)
{
for (int i=0;i<b[x].size();i++)
if (f[b[x][i]]==0) f[b[x][i]]=3,C++;
else if (f[b[x][i]]!=3) flag&=0;
for (int i=0;i<c[x].size();i++)
if (f[c[x][i]]==0) f[c[x][i]]=1,A++;
else if (f[c[x][i]]!=1) flag&=0;
for (int i=0;i<b[x].size();i++)
if (!v[b[x][i]]) flag&=check(b[x][i]);
for (int i=0;i<c[x].size();i++)
if (!v[c[x][i]]) flag&=check(c[x][i]);
}
else
{
for (int i=0;i<b[x].size();i++)
if (f[b[x][i]]==0) f[b[x][i]]=1,A++;
else if (f[b[x][i]]!=1) flag&=0;
for (int i=0;i<c[x].size();i++)
if (f[c[x][i]]==0) f[c[x][i]]=2,B++;
else if (f[c[x][i]]!=2) flag&=0;
for (int i=0;i<b[x].size();i++)
if (!v[b[x][i]]) flag&=check(b[x][i]);
for (int i=0;i<c[x].size();i++)
if (!v[c[x][i]]) flag&=check(c[x][i]);
}
return flag;
}
LL calc()
{
memset(f,0,sizeof(f));
for (int i=1;i<=m;i++)
b[a[i].x].push_back(a[i].y),
c[a[i].y].push_back(a[i].x);
LL ans=0;
for (int i=1;i<=n;i++)
if (b[i].size()>0 && f[i]==0)
{
f[i]=1;A=1,B=0,C=0;S=0;
memset(v,0,sizeof(v));
if (!check(i))
ans+=(A+B+C)*(A+B+C);
else if (C==0) ans+=S/2;
else ans+=(A*B)+(B*C)+(C*A);
}
return ans;
}
int main()
{
read(n);read(m);
for (int i=1;i<=m;i++)
read(a[i].x),read(a[i].y);
print(calc());puts("");
return 0;
}