【AtCoder】AGC031

2019/03/22 14:23
阅读数 102

A - Colorful Subsequence

答案是

$\prod_{c = 'a'}^{'z'} (cnt[c] + 1)$

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 200005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N;
char s[MAXN];
int cnt[35];
void Solve() {
    read(N);
    scanf("%s",s + 1);
    for(int i = 1 ; i <= N ; ++i) {
        cnt[s[i] - 'a']++;
    }
    int res = 1;
    for(int i = 0 ; i < 26 ; ++i) {
        res = 1LL * res * (1 + cnt[i]) % MOD;
    }
    res = (res + MOD - 1) % MOD;
    out(res);enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
    Solve();
}

B - Reversi

记$dp[i][0/1]$表示没有进行操作/进行了操作

$dp[i][0] = dp[i - 1][0] + dp[i - 1][1]$

如果$C[i - 1] == C[i]$,那么不能进行操作

否则可以从前面所有$C[k - 1] != C[k]$且$C[i] == C[k]$的地方转移过来;

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 200005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N,C[MAXN],sum[MAXN];
int dp[MAXN][2];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) {
        read(C[i]);
    }
    dp[0][0] = 1;
    for(int i = 1 ; i <= N ; ++i) {
        dp[i][0] = inc(dp[i - 1][1],dp[i - 1][0]);
        if(C[i] != C[i - 1]) {
            dp[i][1] = sum[C[i]];
            sum[C[i]] = inc(sum[C[i]],dp[i][0]);
        }
    }
    out(inc(dp[N][0],dp[N][1]));enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
    Solve();
}

C - Differ by 1 Bit

这道题用数学归纳法

A和B中1的奇偶性必须不同

显然N = 1的的时候肯定成立

如果$N = K +1$,且$N = K$时成立

这个时候找$A$和$B$中不同的一位,删掉,此时$A$和$B$中1的奇偶性相同

然后现在是两个$K$位数,我们设一个$K$位数$C$,和$A,B$的1的奇偶性不同

然后$A$到$C$可以到达,$C$到$B$也可以达到,递归处理,然后将前$2^K$删掉的位置添加上,且与$A$相同,后$2^{K}$删掉的位置添加上和$B$相同

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 200005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,A,B;
int Delete(int x,int p) {
    int d = x & (1 << p) - 1;
    int u = x & (1 << 20) - (1 << p + 1);
    return (u >> 1) + d;
}
int Insert(int x,int p,int v) {
    int d = x & (1 << p) - 1;
    int u = x & (1 << 20) - (1 << p);
    return (u << 1) + v + d;
}
vector<int> Calc(int s,int t,int n) {
    if(n == 1) {
        vector<int> v;v.pb(s);v.pb(t);
        return v;
    }
    int x = 1,p = 0;
    while(1) {
        if((s & x) != (t & x)) break;
        x <<= 1;++p;
    }
    int a,b;
    a = Delete(s,p);b = Delete(t,p);
    int c = a ^ 1;
    vector<int> f = Calc(a,c,n - 1),h = Calc(c,b,n - 1);
    for(int i = 0 ; i < (1 << n - 1) ; ++i) {
        f[i] = Insert(f[i],p,(s & x));
        h[i] = Insert(h[i],p,(t & x));
    }
    f.insert(f.end(),h.begin(),h.end());
    return f;
}
int count(int x) {
    int res = 0;
    while(x) {
        res += (x & 1);
        x >>= 1;
    }
    return res;
}
void Solve() {
    read(N);read(A);read(B);
    if(!(count(A^B) & 1)) {puts("NO");return;}
    puts("YES");
    vector<int> ans = Calc(A,B,N);
    for(int i = 0 ; i < (1 << N) ; ++i) {
        out(ans[i]);space;
    }
    enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
    Solve();
}

D - A Sequence of Permutations

设$p\cdot q = t$,$t_{i} = p_{q_{i}}$

这里面$a_{2} = q\cdot p^{-1}$

我们把这个写成$a = ABA^{-1}$的形式

可以得到

设$a = (A,B)$

$a_{1} = (id,p)$

$a_{2} = (id,q)$

$a_{3} = (id,qp^{-1})$

$a_{4} = (q,p^{-1})$

$a_5 = (qp^{-1},q^{-1})$

$a_6 = (qp^{-1},q^{-1}p)$

$a_{7} = (qp^{-1}q^{-1}p,p)$

$a_8 = (qp^{-1}q^{-1}p,q)$

发现6次B一个重复

前面是$qp^{-1}q^{-1}p$的$\lfloor \frac{K - 1}{6}\rfloor$次幂

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 100005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,K;
struct pl {
    int f[100005];
    friend pl operator * (const pl &a,const pl &b) {
	pl c;
	for(int i = 1 ; i <= N ; ++i) c.f[i] = a.f[b.f[i]];
	return c;
    }
    pl inv() {
	pl c;
	for(int i = 1 ; i <= N ; ++i) {
	    c.f[f[i]] = i;
	}
	return c;
    }
}p,q,iq,ip,s,res,t,ans;
void fpow(int c) {
    for(int i = 1 ; i <= N ; ++i) res.f[i] = i;
    t = s;
    while(c) {
	if(c & 1) res = res * t;
	t = t * t;
	c >>= 1;
    }
}
void Solve() {
    read(N);read(K);
    for(int i = 1 ; i <= N ; ++i) read(p.f[i]);
    for(int i = 1 ; i <= N ; ++i) read(q.f[i]);
    ip = p.inv();iq = q.inv();
    s = q * ip * iq * p;
    fpow((K - 1) / 6);
    int x = (K - 1) % 6;
    if(x == 0) {
	ans = res * p * res.inv();
    }
    else if(x == 1) {
	ans = res * q * res.inv();
    }
    else if(x == 2) {
	ans = res * q * ip * res.inv();
    }
    else if(x == 3) {
	res = res * q;
	ans = res * ip * res.inv();
    }
    else if(x == 4) {
	res = res * q * ip;
	ans = res * iq * res.inv();
    }
    else if(x == 5) {
	res = res * q * ip;
	ans = res * iq * p * res.inv();
    }
    for(int i = 1 ; i <= N ; ++i) {
	out(ans.f[i]);space;
    }
    enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

E - Snuke the Phantom Thief

假如只能选K个,那么我们可以建出限制

对于一维的,如果是小于等于$a$最多选$b$个,那么相当于第$b+1$个必须在大于等于$a + 1$

如果大于等于$a$最多选$b$个,那么相当于第$K - b$个必须在小于等于$a - 1$处

这样可以对于每一个求一个左右限制出来

满足

$L_{1} \leq L_{2} \leq L_{3}\leq \cdots \leq L_{k}$

$R_{1} \leq R_{2} \leq R_{3} \leq \cdots \leq R_{k}$

然后对两维都求这个限制

建K个点表示x轴上选的第几个,K个点表示y轴上选的第几个

然后2N个点表示每个珠宝各两个点,中间连一条容量为1,价值为珠宝价值的边

然后前K个表示x轴上的点,和x符合条件的珠宝连一条容量为1代价为0的边

然后每个珠宝的第二个点和自身y匹配哪个限制连一条容量为1代价为0的边

然后原点向前K个连一条边,后K个向汇点连一条边,都是容量为1价值为0

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 100005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
struct node {
    int to,next,cap;int64 val;
}E[1000005];
int sumE,head[505],a[330],b[330],x[85],y[85],N,M;
int L[2][85],R[2][85],S,T,f;
int64 val[85],res,ans,ex;
bool vis[505];
char s[330][2];
void add(int u,int v,int c,int64 a) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    E[sumE].cap = c;
    E[sumE].val = a;
    head[u] = sumE;
}
void addtwo(int u,int v,int c,int64 a) {
    add(u,v,c,a);
    add(v,u,0,-a);
}
void build(int K) {
    sumE = 1;memset(head,0,sizeof(head));
    for(int i = 1 ; i <= N ; ++i) L[0][i] = L[1][i] = 1,R[0][i] = R[1][i] = 100;
    for(int i = 1 ; i <= M ; ++i) {
        if(b[i] >= K) continue;
        if(s[i][0] == 'L') {
            L[0][b[i] + 1] = max(L[0][b[i] + 1],a[i] + 1);
        }
        else if(s[i][0] == 'R') {
            R[0][K - b[i]] = min(R[0][K - b[i]],a[i] - 1);
        }
        else if(s[i][0] == 'D') {
            L[1][b[i] + 1] = max(L[1][b[i] + 1],a[i] + 1);
        }
        else if(s[i][0] == 'U') {
            R[1][K - b[i]] = min(R[1][K - b[i]],a[i] - 1);
        }
    }
    for(int i = 2 ; i <= K ; ++i) {
    	L[0][i] = max(L[0][i - 1],L[0][i]);
    	L[1][i] = max(L[1][i - 1],L[1][i]);
    }
    for(int i = K - 1 ; i >= 1 ; --i) {
    	R[0][i] = min(R[0][i + 1],R[0][i]);
    	R[1][i] = min(R[1][i + 1],R[1][i]);
    }
    S = 1;T = 2 * K + 2 * N + 2;
    for(int i = 1 ; i <= K ; ++i) {
    	addtwo(S,i + 1,1,0);
    	addtwo(i + K + 2 * N + 1,T,1,0);
    	for(int j = 1 ; j <= N ; ++j) {
    	    if(x[j] >= L[0][i] && x[j] <= R[0][i]) {
        		addtwo(i + 1,K + j + 1,1,0);
    	    }
    	    if(y[j] >= L[1][i] && y[j] <= R[1][i]) {
        		addtwo(K + N + j + 1,i + K + 2 * N + 1,1,0);
    	    }
    	}
    }
    for(int i = 1 ; i <= N ; ++i) {
        addtwo(K + i + 1,K + N + i + 1,1,val[i]);
    }

}
int maxflow(int u,int aug) {
    if(u == T) {
    	res += ex * aug;
        f += aug;
    	return aug;
    }
    int flow = 0;
    vis[u] = 1;
    for(int i = head[u] ; i ; i = E[i].next) {
        int v = E[i].to;
    	if(E[i].cap > 0 && !vis[v] && E[i].val == 0) {
    	    int t = maxflow(v,min(E[i].cap,aug - flow));
    	    flow += t;
    	    E[i].cap -= t;
    	    E[i ^ 1].cap += t;
    	}
    }
    return flow;
}
bool modlabel() {
    int64 p = -1e18;
    for(int u = S ; u <= T ; ++u) {
    	if(vis[u]) {
    	    for(int i = head[u] ; i ; i = E[i].next) {
        		int v = E[i].to;
        		if(!vis[v] && E[i].cap > 0 && E[i].val > p) p = E[i].val;
    	    }
    	}
    }
    if(p == -1e18) return false;
    ex += p;
    for(int u = S ; u <= T ; ++u) {
    	if(vis[u]) {
    	    for(int i = head[u] ; i ; i = E[i].next) {
        		E[i].val -= p;
        		E[i ^ 1].val += p;
    	    }
    	}
    }
    return true;
}
void Init() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) {
    	read(x[i]);read(y[i]);read(val[i]);
    }
    read(M);
    for(int i = 1 ; i <= M ; ++i) {
    	scanf("%s",s[i]);read(a[i]);read(b[i]);
    }
}
void Solve() {
    ans = 0;
    for(int i = 1 ; i <= N ; ++i) {
    	build(i);
    	res = 0;ex = 0;
        f = 0;
    	do {
    	    do {
                memset(vis,0,sizeof(vis));
    	    }while(maxflow(1,i));
    	}while(modlabel());
        if(f == i) ans = max(ans,res);
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Init();
    Solve();
}

F - Walk on Graph

这道题特别神仙


反着来考虑,我们设$(v,x)$表示$v$这个点有价值为$x$,那么如果有一条边$(u,v,c)$,那么我们可以走到的状态是$(u,2x +c) \rightarrow (v,4x + 3c) \rightarrow (u,8x + 7c)\cdots$

因为模数是奇数嘛,这么乘下去,一定会得到$1$的,感性理解可参照费马小定理

那么我们就知道了

$(v,x)\rightarrow(u,2x + c)$

$(u,2x+c)\rightarrow(v,x)$

这是一个双射


然后就是,如果一个点有代价为$a$和代价为$b$的边直接相连,那么它可以走到

$(v,x)\Leftrightarrow (v,4x + 3a)$

$(v,x)\Leftrightarrow (v,4x + 3a)$

我们可以选择这条路

$(v,4x + 3a) \rightarrow (v,x) \rightarrow(v,4x + 3b)$

事实上,我们存在对4的逆元,那么$4x$可以表示任何数,那么我们就又得到了一条性质

$(v,x) \rightarrow (v,x + 3k(a - b)),k \in \Z$


如果我们对于所有的边权之差和MOD求一个gcd,设为$g$,$g|a - b$且$g|b - c$那么$g|a - c$所以这个$g$可以通过每条边减第一条边的绝对值的和MOD求gcd获得

事实上,我们的运算可以在$gcd(MOD,3g)$意义下进行

为什么呢,显然我们的模数要么是$g$要么是$3g$

如果是$g$的话,$MOD$和$3$互质,且一定存在两个不同的边权之差$a - b$和$d - c$互质,图是联通的,我们可以通过这两个互质的边权之差构造出,根据同余方程,然后这个时候和3又互质,所以3存在逆元,我们又可以构造出任意数,所以模$g$意义下相等的就都相等了

$3g$也是同理的。。。

好的,这个问题解决了,那么我们修改了模数后,所有的边权都相等了


那么现在有个问题,如果$(v,x)\rightarrow (u,2x + c)$

现在我们是$(v,x)\rightarrow (u,2x + z + pg),(0 \leq p < 3)$

看起来问题没什么实质性解决

但是如果我们认为$x' = x + z$边权减去$z$

从$x \rightarrow 2x + z + pg$

就是$x' \rightarrow 2x' + pg = 2x + 2z + pg - z$

这样的话边权都是g的倍数了,也满足$(v,x) \rightarrow (v,2x + c)$

这样看起来很棒,那么就这样吧

于是我们的询问可以从$(t,z)$到$(s,r + z)$


那么一个点可以被表示成

因为$(v,x) \rightarrow (v,4x + 3c)$,而且$c$又是$g$的倍数,那么认为$(v,x) \rightarrow(v,4x)$

那么就有$(v,2^{q}x + pg)$,$(0\leq q \leq 1,0 \leq p \leq 2)$

这样图里只有6个点了,我们可以用并查集连一下


查询的时候

查$(t,x)$和$(s,2^{p}x + qg)$是否连通

这个可以得到

$2^{p}z + qg = r + z$

那么看一下$r + z - qg$是2的奇数次幂乘$x$还是2的偶数次幂乘$x$

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int maxn = 5e5 + 5,maxm = 1e6 + 5;;

int N,M,Q,MOD,f[maxn],t[maxn],v[maxn];
int fa[maxm * 6],z,g;
bool able[2][maxm];
int id(int u,int p,int q) {
    return (u - 1) * 6 + p * 3 + q + 1;
}
int gcd(int a,int b) {
    return b == 0 ? a : gcd(b,a % b);
}
int getfa(int u) {
    return u == fa[u] ? u : fa[u] = getfa(fa[u]);
}
void Merge(int u,int v) {
    fa[getfa(u)] = getfa(v);
}
void Init() {
    read(N);read(M);read(Q);read(MOD);
    read(f[1]);read(t[1]);read(v[1]);
    g = MOD;
    for(int i = 2 ; i <= M ; ++i) {
	read(f[i]);read(t[i]);read(v[i]);
	g = gcd(g,abs(v[i] - v[1]));
    }
    MOD = gcd(MOD,3 * g);
    z = v[1] % g;
    int T = id(N,1,2);
    for(int i = 1 ; i <= T; ++i) fa[i] = i;
    for(int i = 1 ; i <= M ; ++i) {
	int w = (v[i] / g) % 3;
	for(int p = 0 ; p < 2 ; ++p) {
	    for(int q = 0 ; q < 3 ; ++q) {
		Merge(id(f[i],p,q),id(t[i],p ^ 1,(q * 2 + w) % 3));
		Merge(id(t[i],p,q),id(f[i],p ^ 1,(q * 2 + w) % 3));
	    }
	}
    }
    for(int i = 0 , j = z ; i < MOD ; ++i , j = j * 2 % MOD) able[i & 1][j] = 1;
}
void Solve() {
    int s,t,r;
    for(int i = 1 ; i <= Q ; ++i) {
	read(s);read(t);read(r);
	bool res = 0;
	for(int p = 0 ; p < 2 ; ++p) {
	    for(int q = 0 ; q < 3 ; ++q) {
		if(getfa(id(t,0,0)) == getfa(id(s,p,q))) {
		    if(able[p][(r + z + (3 - q) * g) % MOD]) res = 1;
		}
	    }
	}
	if(res) puts("YES");
	else puts("NO");
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Init();
    Solve();
}
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部