AGC031题解

Source

AGC031

参考

zsy
sjq

A

请先思考后再展开

每种颜色大小+1的乘积-1

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
#define PB push_back
inline void chmax(ll &x,ll y) {x=x>y?x:y;}
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
const int MOD=1e9+7;
const int MAX_N=1e5+10;
char s[MAX_N];
int f[30];
void main()
{
int n;scanf("%d",&n);
scanf("%s",s+1);for(int i=1;i<=n;i++) f[s[i]-'a']++;
ll ans=1;for(int i=0;i<26;i++) ans=ans*(f[i]+1)%MOD;
printf("%lld",(ans+MOD-1)%MOD);
}
};
int main()
{
srand(time(0));
mine::main();
}

B

请先思考后再展开

凭直觉想到的……
就是我们希望找到多少种不同的操作序列,然后注意到真正有意义的操作是互不重叠的
然后如果一个操作能被多个操作等效替代,或者不操作也行,那么是没有意义的
所以我们只需要考虑互不重叠的、中间没有这个颜色的、长度>2的操作即可
设f(i)表示考虑了前i位,而且最后一次操作的右端点在i
这个dp用前缀和优化一下就是线性的

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
#define PB push_back
inline void chmax(ll &x,ll y) {x=x>y?x:y;}
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
const int MAX_N=2e5+10;
int c[MAX_N],lst[MAX_N],pos[MAX_N];
const int MOD=1e9+7;
ll f[MAX_N],g[MAX_N];
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
c[i]=qread();
lst[i]=pos[c[i]];
pos[c[i]]=i;
}
f[0]=g[0]=1;
for(int i=1;i<=n;i++)
{
int j=lst[i];
if(j<i-1 and j!=0) f[i]=g[j];
g[i]=(g[i-1]+f[i])%MOD;
}
printf("%lld",g[n]);
}
};
int main()
{
srand(time(0));
mine::main();
}

C

请先思考后再展开

$2^n个数,变化2^n-1次,为奇数,故A和B的popcount奇偶性不同$
考虑以构造的方式证明,当A和B满足上述条件时,至少有一组方案
归纳法,n=1显然成立,然后假设n=k成立,现在尝试做n=k+1
去掉A和B的某个不同位置后,A和B的popcount奇偶性相同,然后我们令C为与当前A差一位的数
那么我们到n=k下,得出A->C和C->B,然后左边插入A少的那一位,右边插入B少的那一位
然后这样就能满足奇偶性的那个性质了
代码实现也是类似这样归纳,时间复杂度为 $O(n2^n)$

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
inline void chmax(ll &x,ll y) {x=x>y?x:y;}
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
int bin[30],ct[1<<21];
vector<int> ans[30];
int lowbit(int x) {return x&-x;}
void solve(int mask,int a,int b)
{
int len=ct[mask];
ans[len].resize(0);
if(len==1){ans[len].PB(a&mask);ans[len].PB(b&mask);return;}
int k=lowbit((a^b)&mask),c=a^lowbit(mask^k);
solve(mask^k,a,c);for(int t=0;t<(int)ans[len-1].size();t++) ans[len].PB(ans[len-1][t]^(a&k));
solve(mask^k,c,b);for(int t=0;t<(int)ans[len-1].size();t++) ans[len].PB(ans[len-1][t]^(b&k));
}
void main()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
for(int i=1;i<=bin[20];i++) ct[i]=ct[i>>1]+(i&1);
int n,a,b;scanf("%d%d%d",&n,&a,&b);
if((ct[a]&1)==(ct[b]&1)) {puts("NO");return;}
puts("YES");solve(bin[n]-1,a,b);
for(int t=0;t<(int)ans[n].size();t++) printf("%d ",ans[n][t]);
}
};
int main()
{
srand(time(0));
mine::main();
}

D

请先思考后再展开

看到这题后,就想着应该要用公式化的语言,找到一些规律什么的……但不知道怎么表达这个操作
随便手画了一个n=3发现循环节是6但没敢画下去了,嫌麻烦……

我们定义排列的乘法: $pq=A,A[i]=p_q_i$
那么我们自然希望 $A \times 1=A$ 故1应为递增的序列
注意这个东西是不满足交换律的,所以做除法的时候顺序要倒过来
那么逆元也是可求的

$[f(p,q)]_p_i=q_i,f(p,q)p=q,f(p,q)=qp^{-1}$
然后把前面若干项列出来
$$
a_1=p\a_2=q\a_3=qp^{-1}\a_4=qp^{-1}q^{-1}\a_5=qp^{-1}q^{-1}pq^{-1}\a_6=qp^{-1}q^{-1}ppq^{-1}\a_7=qp^{-1}q^{-1}pqpq^{-1}\a_8=qp^{-1}q^{-1}pqp^{-1}qpq^{-1}$$
然后你会发现 $A=qp^{-1}q^{-1}p,a_n=Aa_{n-6}A^{-1}$

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
inline void chmax(ll &x,ll y) {x=x>y?x:y;}
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
const int MAX_N=1e5+10;
struct PP
{
int m[MAX_N];PP(){memset(m,0,sizeof m);}
int& operator [] (int i) {return m[i];}
PP inv()
{
PP b;for(int i=1;i<MAX_N;i++) b[m[i]]=i;
return b;
}
friend PP operator * (PP a,PP b)
{
PP c;for(int i=1;i<MAX_N;i++) c[i]=a[b[i]];
return c;
}
friend PP operator / (PP a,PP b)
{
return a*b.inv();
}
};
PP qpower(PP x,int e)
{
PP ans;for(int i=1;i<MAX_N;i++) ans[i]=i;
while(e)
{
if(e&1) ans=ans*x;
x=x*x;e>>=1;
}
return ans;
}
PP a[10],A,ans;
void main()
{
int n,k;scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) a[1][i]=qread();
for(int i=1;i<=n;i++) a[2][i]=qread();
a[0]=a[2].inv()*a[1];for(int i=3;i<=5;i++) a[i]=a[i-1]/a[i-2];
A=a[2]/a[1]/a[2]*a[1];ans=qpower(A,k/6)*a[k%6]/qpower(A,k/6);
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
}
};
int main()
{
srand(time(0));
mine::main();
}

E

请先思考后再展开

枚举最后选了T个

先考虑只有一维的情况
$$
\begin{aligned}
&L:[x \leq a_i] \leq b_i \to A[b_i+1]>a_i\\
&R:[x \geq a_i] \leq b_i \to A[T-b_i] \leq a_i-1\\
&注意这里不能死板地认为二分图中L_i选择的就是第i个珠子\\
&那么你会发现推一下标记即可得到连边的不重叠区间,如果重叠就不能这么做了
\end{aligned}
$$

二维的话,左右都有限制,类似于每个点在两侧占用配额
权值拆点即可

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=1100,MAX_M=1e5;
int hou[MAX_N];
struct Edge{int y,g,c;ll w;}e[MAX_M*2];
int ln=0;int oth(int x){return x&1?x+1:x-1;}
void ins(int x,int y,int c,ll w)
{
if(c==0) return;
e[++ln]=(Edge){y,hou[x],c,w};hou[x]=ln;
e[++ln]=(Edge){x,hou[y],0,-w};hou[y]=ln;
}
int st,ed;queue<int> qq;bool v[MAX_N];
ll dis[MAX_N];int fm[MAX_N],mic[MAX_N];
ll ans;int flow;
bool solve()
{
memset(dis,-0x3f,sizeof dis);
memset(v,0,sizeof v);v[st]=1;
qq.push(st);mic[st]=INF;dis[st]=0;
while(qq.size())
{
int x=qq.front();qq.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(dis[y]<dis[x]+e[k].w and e[k].c)
{
dis[y]=dis[x]+e[k].w;
mic[y]=min(mic[x],e[k].c);fm[y]=k;
if(!v[y]) v[y]=1,qq.push(y);
}
}
v[x]=0;
}
if(mic[ed]==0 or dis[ed]<0) return 0;
ans+=dis[ed]*mic[ed];flow+=mic[ed];
for(int x=ed;x!=st;x=e[oth(fm[x])].y) e[fm[x]].c-=mic[ed],e[oth(fm[x])].c+=mic[ed];
return 1;
}
int n,m;ll val[MAX_N];
pr pt[MAX_N];struct Qes{int a,b;char op[10];}q[MAX_N];
int fl[2][MAX_N],fr[2][MAX_N];
ll getans(int T)
{
ln=0;memset(hou,0,sizeof hou);st=0,ed=n*4+1;
for(int i=1;i<=n;i++) ins(i,n+i,1,val[i]);
memset(fl,0,sizeof fl);memset(fr,0x3f,sizeof fr);fl[0][1]=1;fr[0][T]=100;fl[1][1]=1;fr[1][T]=100;
for(int i=1;i<=m;i++) if(q[i].b<T)
{
if(q[i].op[0]=='L') chmax(fl[0][q[i].b+1],q[i].a+1);
if(q[i].op[0]=='R') chmin(fr[0][T-q[i].b],q[i].a-1);
if(q[i].op[0]=='D') chmax(fl[1][q[i].b+1],q[i].a+1);
if(q[i].op[0]=='U') chmin(fr[1][T-q[i].b],q[i].a-1);
}
for(int i=1;i<T;i++) chmax(fl[0][i+1],fl[0][i]);for(int i=T;i>=2;i--) chmin(fr[0][i-1],fr[0][i]);
for(int i=1;i<=T;i++)
{
ins(st,n*2+i,1,0);
for(int j=1;j<=n;j++) if(fl[0][i]<=pt[j].FR and pt[j].FR<=fr[0][i]) ins(n*2+i,j,1,0);
}
for(int i=1;i<T;i++) chmax(fl[1][i+1],fl[1][i]);for(int i=T;i>=2;i--) chmin(fr[1][i-1],fr[1][i]);
for(int i=1;i<=T;i++)
{
ins(n*3+i,ed,1,0);
for(int j=1;j<=n;j++) if(fl[1][i]<=pt[j].SE and pt[j].SE<=fr[1][i]) ins(n+j,n*3+i,1,0);
}
ans=0;flow=0;while(solve()) ;
return ans*(flow==T);
}
void main()
{
n=qread();for(int i=1;i<=n;i++) scanf("%d%d%lld",&pt[i].FR,&pt[i].SE,&val[i]);
m=qread();for(int i=1;i<=m;i++) scanf("%s%d%d",q[i].op,&q[i].a,&q[i].b);
ll ans=0;for(int T=1;T<=n;T++) ans=max(ans,getans(T));
printf("%lld",ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

F

请先思考后再展开

有个比较巧妙的转化:因为代价是个多项式的形式,可以联想到秦九韶
正着走,那么代价会和点、第几条边、当前和有关,但倒着走则只和当前点、当前和有关(a->2a+c)
那么相当于有n乘mod个点,要求判断可达性

考虑这个模型的特殊性质:

  1. 边是双向的,如果不停经过同一条边, $2^{MOD-1}=1,MOD-1为偶数,且c前面的常数总是a系数-1,则回到a是一个偶环,所以会恰好回到(x,a)$
  2. 考虑同一个点旁边的两条边,(x,4a+3n)与(x,4n+3m)等价,即可以任意加上3(n-m)
    那么这个就是在模M意义下,存在某个跨度T的经典模型
    考虑到回到原地需要lcm(M,T)/T步,即存在gcd(M,T)个环,且由裴蜀定理知与x同个环的序列上下个元素,与x的差为gcd(M,T)
    故可以把0~gcd(M,T)-1作为每个环的起点,即可以 $M \gets gcd(M,T)$
    又因为图是联通的,那么每两条边都能影响整个图的所有点,$(x,a)与(x,a+3g)等价,g=所有边的差与MOD的gcd$
    $g|a-b且g|a-c \to g|b-c$ ,所以这个g可以通过所有边和第一条边的差与MOD的gcd得到
    (注意这里我可以直接说a与a+gcd(边差,MOD),但为了后面方便用a+gcd(3gcd(边差,MOD),MOD)显然没影响)

于是M=g或3g,此时边权%g相同=z,考虑所有边权-=z,然后状态+=z
不难证明这样是等价的,只不过我们需要询问的是(st,z)->(ed,r+z)
此时所有边都是g的倍数,边的部分的影响就是 $bg(0 \leq b \leq 2)$
除此之外我们关心的就是z,z->2z+c->4z+3c,故可表示为 $az(1 \leq a \leq 2)$ ,这里1z表示系数为2的奇数次幂
于是现在图上面只有6n个状态了……

需要预处理一下z前2的次幂可达状态

忘记翻转ed和st,调了很久……

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
inline void chmax(ll &x,const ll y) {x=x>y?x:y;}
inline void chmin(ll &x,const ll y) {x=x<y?x:y;}
const int MAX_N=5e5+10;
struct DSU
{
int fa[MAX_N];DSU(){for(int i=0;i<MAX_N;i++) fa[i]=i;}
int findfa(int x) {return x==fa[x]?x:fa[x]=findfa(fa[x]);}
bool okay(int x,int y) {return findfa(x)==findfa(y);}
void merg(int x,int y) {fa[findfa(x)]=findfa(y);}
}dsu;
int gcd(int x,int y) {return y==0?x:gcd(y,x%y);}
struct Edge{int x,y,c;}e[MAX_N];
int calc(int x,int a,int b){return 6*(x-1)+3*a+b;}
bool tmp[2][1100000];
void main()
{
int n,m,q,M;scanf("%d%d%d%d",&n,&m,&q,&M);int g=M;
for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c),g=gcd(g,abs(e[i].c-e[1].c));
M=gcd(M,3*g);int z=e[1].c%g;
for(int i=1;i<=m;i++)
{
int x=e[i].x,y=e[i].y,c=(e[i].c-z)/g;
for(int a=0;a<=1;a++) for(int b=0;b<=2;b++)
{
dsu.merg(calc(x,a,b),calc(y,a^1,(b*2+c)%3));
dsu.merg(calc(y,a,b),calc(x,a^1,(b*2+c)%3));
}
}
for(int i=0,j=z;i<M;i++,j=j*2%M) tmp[i&1][j]=1;
while(q--)
{
int x,y,r;scanf("%d%d%d",&x,&y,&r);
bool bk=0;
for(int a=0;a<=1;a++) for(int b=0;b<=2;b++)
if(dsu.okay(calc(y,0,0),calc(x,a,b)) and tmp[a][ (r+z+(3-b)*g)%M ]) bk=1;
puts(bk?"YES":"NO");
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6c0c.html
转载请注明出处,谢谢!