CodeforcesRound454

冒着爆肝的危险和第二天模拟赛爆蛋的危险打了一发深夜场,

然后第二天模拟赛果然爆蛋了。

不要在意tag里的仙人掌,等下我会细说的。

由于没人打div2,就开那个离div2就差2分的大号去打div1了。

小猪临时变卦去睡觉啦然后就只剩下我和旺仔啊。

T1:给你一棵树在不同深度上个点数,要求构造一种方案使得两个树本质不相等。

考虑本质不相等的方案,显然可以看出至少有一层所有的结点度数本质不相等,也就是说下一层至少要多于一个,本层至少也要多于一个。故方案易得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
inline int read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int k=1,kk=0;if (c=='-')c=getchar(),k=-1;
while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(int x){if (x)write(x/10),putchar(x%10+'0');}
void writeln(int x){if (x<0)putchar('-'),x=-x;write(x);if (x==0)putchar('0');puts("");}
int n,a[1000000],kk;
int main(){
n=read()+1;for (int i=1;i<=n;i++){
a[i]=read();if (a[i]>1&&a[i-1]>1)kk=i;
}if (!kk)puts("perfect");else {
puts("ambiguous");
for (int i=1;i<=n;i++){
for (int j=1;j<=a[i];j++)cout<<a[i-1]<<' ';
a[i]+=a[i-1];
} cout<<endl;
for (int i=1;i<=n;i++){
for (int j=a[i-1]+1;j<=a[i];j++)
if (i!=kk||j!=a[i])cout<<a[i-1]<<' ';
else cout<<a[i-1]-1<<' ';
} cout<<endl;
}
}

T2 构造两个系数的绝对值最多为1的n次多项式,要求两多项式可以被互相取余n次。

显然可以发现,因为多项式次数和辗转相除的次数是相等的,所得的商必然为x或者-x。

然后就没有更好的办法了,猜结论呗。其实算法的正确性是可以写个程序检验小于150的是否合法的,毕竟n比较小啊。

r爷认为这题是这场比赛最难的一题。lca貌似推了一万年结论。

大概就是每次乘以x,然后加上去啊,大于2就取余啊。

好像减去之后大于2变成0,小于-2变成0也是对的(skydec就是这么写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
inline int read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int k=1,kk=0;if (c=='-')c=getchar(),k=-1;
while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(int x){if (x)write(x/10),putchar(x%10+'0');}
void writeln(int x){if (x<0)putchar('-'),x=-x;write(x);if (x==0)putchar('0');puts("");}
int n,x[1000],y[1000],xx,yy;
int main(){
n=read();x[0]=1;
for (int i=1;i<=n;i++){
for (int j=0;j<=xx;j++)(y[j+1]+=x[j])%=2;
yy=max(yy,xx+1);swap(xx,yy);for (int j=0;j<=xx;j++)swap(x[j],y[j]);
}while (!x[xx])xx--;while (!y[yy])yy--;
cout<<xx<<endl;for (int i=0;i<=xx;i++)cout<<x[i]<<' ';cout<<endl;
cout<<yy<<endl;for (int i=0;i<=yy;i++)cout<<y[i]<<' ';cout<<endl;
}

T3 :给你一张无向图,保证只有长度为奇数的环,查询区间l,r中有多少点对x,y之间的点的点集是一张二分图。

奇环是个很好的性质啊。

有奇环显然没有二分图没有奇环显然有二分图。因为是奇环所以不存在两个相交的环(也就是仙人掌。

所以每个点最多属于一个环我们可以用dfs预处理出来那个点所在的环。

所以考虑预处理每个点最右边可以取到的点,然后二分一发答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define int long long
inline int read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int k=1,kk=0;if (c=='-')c=getchar(),k=-1;
while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(int x){if (x)write(x/10),putchar(x%10+'0');}
void writeln(int x){if (x<0)putchar('-'),x=-x;write(x);if (x==0)putchar('0');puts("");}
int n,m,x,y,a[1000000][2],last[1000000],f[1000000],dd[1000000],d[1000000],ff[1000000],b[1000000],kk,l,r,q;
bool flag[1000000],fk[1000000];
int fa(int x){return f[x]==x?x:f[x]=fa(f[x]);}
int dfs(int x,int fh,int de){
dd[de]=x;flag[x]=1;fk[x]=1;
for (int i=last[x];i;i=a[i][0])if (a[i][1]!=fh&&(!fk[a[i][1]]||flag[a[i][1]])){
if (!flag[a[i][1]])dfs(a[i][1],x,de+1);
else{
int ddd=de;d[x]=1;
while (dd[ddd]!=a[i][1]){
ddd--;f[dd[ddd]]=x;d[x]++;
}
}
}flag[x]=0;if (!d[fa(x)])f[x]=0;
}void doit(int x,int y){a[++kk][0]=last[x];a[kk][1]=y;last[x]=kk;}
signed main(){
n=read();m=read();for (int i=1;i<=m;i++)x=read(),y=read(),doit(x,y),doit(y,x);
for (int i=1;i<=n;i++)f[i]=i;
for (int i=1;i<=n;i++)if (!flag[i])dfs(i,0,1);d[0]=1e9;r=0;
for (int i=1;i<=n;i++){
while (d[fa(r)]>1&&r<=n)d[fa(r)]--,r++;ff[i]=r-1;d[fa(i)]++;
}for (int i=1;i<=n;i++)b[i]=b[i-1]+ff[i]-i+1;
q=read();while (q--){
x=read();y=read();l=x;r=y;while (l<r){
int m=(l+r)/2;if (ff[m]>=y)r=m;else l=m+1;
}writeln(b[l-1]-b[x-1]+(y-l+1)*(y-l+2)/2);
}
}

剩下的留坑(逃

我以后如果没事干了记得提醒我这里还有个坑

分享到