AtCoder Beginner Contest 271 Solution更好的阅读体验戳此进入题面链接题面 Luogu 链接abc 跳了[ABC271D] Flip and Adjust题面SolutionCode[ABC271E] Subsequence Path题面SolutionCode[ABC271F] XOR on Grid Path题面SolutionCode[ABC271G] Access Counter题面SolutionCode[ABC271Ex] General General题面SolutionCodeUPD
给定 No
,反之输出 Yes
并输出任意方案。
一般的思路都是 DP 同时记录决策点然后最后跑一遍答案,不过这样还需要动脑,本题范围较小不如暴力一点,我们直接在 DP 过程中的每一个状态记录所有牌的正反,最开始的思路是开一个 bitset
这样多出来的复杂度是 basic_string < char >
无脑维护就行了,这样转移会多一个复制的 1e8
。
转移显然:
然后中间判断一下是否能转移,也就是
xxxxxxxxxx
611
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23template < typename T = int >
24inline T read(void);
25
26int N, S;
27int A[110], B[110];
28basic_string < char> dp[110][11000];
29
30int main(){
31 N = read(), S = read();
32 for(int i = 1; i <= N; ++i)A[i] = read(), B[i] = read();
33 dp[1][A[1]] += 'H', dp[1][B[1]] += 'T';
34 for(int i = 2; i <= N; ++i)
35 for(int j = 0; j <= S; ++j){
36 if(j - A[i] >= 0 && (int)dp[i - 1][j - A[i]].size() == i - 1)dp[i][j] = dp[i - 1][j - A[i]] + 'H';
37 if(j - B[i] >= 0 && (int)dp[i - 1][j - B[i]].size() == i - 1)dp[i][j] = dp[i - 1][j - B[i]] + 'T';
38 }
39 if((int)dp[N][S].size() != N)printf("No\n"), exit(0);
40 printf("Yes\n");
41 for(auto v : dp[N][S])printf("%c", v);
42 printf("\n");
43 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44 return 0;
45}
46
47template < typename T >
48inline T read(void){
49 T ret(0);
50 int flag(1);
51 char c = getchar();
52 while(c != '-' && !isdigit(c))c = getchar();
53 if(c == '-')flag = -1, c = getchar();
54 while(isdigit(c)){
55 ret *= 10;
56 ret += int(c - '0');
57 c = getchar();
58 }
59 ret *= flag;
60 return ret;
61}
给定 -1
。
最开始的思路是把边集下放然后每个点挂多个 pair < ll, int >
表示到这个点的所有可能的权值与其对应的最小的序列终止位置,然后用类似二维偏序的思路转移,但是不确定这个思路假没假以及复杂度是否正确,不过细想一下就会发现这题实际上特别水。
不难发现我们要找的是边的子序列,也就是其是有顺序的,那么我们直接按照边序列顺序跑的话显然是无后效性的,所以我们可以按照最短路的思想,考虑记录到每个点的
xxxxxxxxxx
591
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28int N, M, K;
29struct{int s, t, v;}edg[210000];
30ll dis[210000];
31
32int main(){
33 memset(dis, 0x3f, sizeof dis);
34 N = read(), M = read(), K = read();
35 for(int i = 1; i <= M; ++i)edg[i].s = read(), edg[i].t = read(), edg[i].v = read();
36 dis[1] = 0;
37 for(int i = 1; i <= K; ++i){
38 int idx = read();
39 dis[edg[idx].t] = min(dis[edg[idx].t], dis[edg[idx].s] + edg[idx].v);
40 }printf("%lld\n", dis[N] == INFLL ? -1ll : dis[N]);
41 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
42 return 0;
43}
44
45template < typename T >
46inline T read(void){
47 T ret(0);
48 int flag(1);
49 char c = getchar();
50 while(c != '-' && !isdigit(c))c = getchar();
51 if(c == '-')flag = -1, c = getchar();
52 while(isdigit(c)){
53 ret *= 10;
54 ret += int(c - '0');
55 c = getchar();
56 }
57 ret *= flag;
58 return ret;
59}
给定一个n行n列的矩阵,定义合法路径为只向右或向下的路径,且途径数字异或和为0。求合法路径条数。
经典 meet in the middle,记录跑到对角线上的值然后合并即可,复杂度大概是
xxxxxxxxxx
751
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28int N;
29int A[50][50];
30ll ans(0);
31unordered_map < int, int > Scnt[50][50], Tcnt[50][50];
32
33void dfs_S(int x = 1, int y = 1, int cur = A[1][1]){
34 if(x > N || y > N || x + y > N + 1)return;
35 // printf("S dfs %d %d, cur = %d\n", x, y, cur);
36 if(x + y == N + 1)Scnt[x][y][cur]++;
37 dfs_S(x + 1, y, cur ^ A[x + 1][y]);
38 dfs_S(x, y + 1, cur ^ A[x][y + 1]);
39}
40void dfs_T(int x = N, int y = N, int cur = A[N][N]){
41 if(x < 1 || y < 1 || x + y < N + 1)return;
42 // printf("T dfs %d %d, cur = %d\n", x, y, cur);
43 if(x + y == N + 1)Tcnt[x][y][cur]++;
44 dfs_T(x - 1, y, cur ^ A[x - 1][y]);
45 dfs_T(x, y - 1, cur ^ A[x][y - 1]);
46}
47
48int main(){
49 N = read();
50 for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)A[i][j] = read();
51 dfs_S(), dfs_T();
52 for(int i = 1; i <= N; ++i){
53 int X = i, Y = N - i + 1;
54 for(auto mp : Scnt[X][Y])ans += (ll)mp.second * Tcnt[X][Y][mp.first ^ A[X][Y]];
55 }
56 printf("%lld\n", ans);
57 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
58 return 0;
59}
60
61template < typename T >
62inline T read(void){
63 T ret(0);
64 int flag(1);
65 char c = getchar();
66 while(c != '-' && !isdigit(c))c = getchar();
67 if(c == '-')flag = -1, c = getchar();
68 while(isdigit(c)){
69 ret *= 10;
70 ret += int(c - '0');
71 c = getchar();
72 }
73 ret *= flag;
74 return ret;
75}
每天存在 A
和 T
组成的长度为 T
则 Taka 有 A
则 Aoki 有
首先看一眼这个题面与
一个显而易见但较为重要的性质,即两次访问之间间隔的天数是易于统计的,重要的在于两次访问的时间点
令对应时间点的访问成功概率为
显然和式为等比数列求和,且由题意可知公比
显然
于是我们完成了
令
按照我们之前的想法挂到矩阵上:
显然
答案统计一下所有
xxxxxxxxxx
1441
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28ll N;
29ll Taka, Aoki;
30ll p[30];
31ll P(1);
32ll ansv(0);
33ll inv100;
34ll dp[30][30];
35bitset < 30 > belong;
36
37ll qpow(ll a, ll b){
38 ll ret(1), mul(a);
39 while(b){
40 if(b & 1)ret = ret * mul % MOD;
41 b >>= 1;
42 mul = mul * mul % MOD;
43 }return ret;
44}
45
46class Matrix{
47private:
48 int siz;
49 ll v[30][30];
50public:
51 Matrix(int len = 24, int pat = 0){
52 siz = len;
53 for(int i = 0; i < siz; ++i)
54 for(int j = 0; j < siz; ++j)
55 v[i][j] = 0;
56 switch(pat){
57 case 1:{
58 for(int i = 0; i < siz; ++i)v[i][i] = 1;
59 break;
60 }
61 case 2:{
62 v[0][siz - 1] = 1;
63 break;
64 }
65 case 3:{
66 for(int i = 1; i <= siz; ++i)
67 for(int j = 1; j <= siz; ++j)
68 v[i - 1][j - 1] = dp[i][j];
69 break;
70 }
71 default: break;
72 }
73 }
74 friend Matrix operator * (const Matrix &a, const Matrix &b){
75 Matrix ret(24);
76 for(int i = 0; i < 24; ++i)
77 for(int j = 0; j < 24; ++j)
78 for(int k = 0; k < 24; ++k)
79 (ret.v[i][j] += a.v[i][k] * b.v[k][j] % MOD) %= MOD;
80 return ret;
81 }
82 void SetAns(void){
83 for(int i = 0; i < 24; ++i)
84 if(belong[i + 1])(ansv += v[0][i]) %= MOD;
85 }
86 void Print(void){
87 printf("##########\n");
88 for(int i = 0; i < siz; ++i)
89 for(int j = 0; j < siz; ++j)
90 printf("%lld%c", v[i][j], j == siz - 1 ? '\n' : ' ');
91 printf("##########\n");
92 }
93}ans(24, 2);
94
95Matrix qpow(Matrix a, ll b){
96 Matrix ret(24, 1), mul(a);
97 while(b){
98 if(b & 1)ret = ret * mul;
99 b >>= 1;
100 mul = mul * mul;
101 }return ret;
102}
103
104int main(){
105 inv100 = qpow(100, MOD - 2);
106 N = read < ll >(), Taka = read(), Aoki = read();
107 for(int i = 1; i <= 24; ++i){
108 char c = getchar(); while(!isalpha(c))c = getchar();
109 p[i] = c == 'T' ? Taka : Aoki, belong[i] = c == 'T' ? false : true;
110 (P *= (100 - p[i]) * inv100 % MOD) %= MOD;
111 }
112 for(int i = 1; i <= 24; ++i){
113 for(int j = 1; j <= 24; ++j){
114 ll R(1);
115 if(i < j)for(int k = i + 1; k <= j - 1; ++k)(R *= (100 - p[k]) * inv100 % MOD) %= MOD;
116 else{
117 for(int k = i + 1; k <= 24; ++k)(R *= (100 - p[k]) * inv100 % MOD) %= MOD;
118 for(int k = 1; k <= j - 1; ++k)(R *= (100 - p[k]) * inv100 % MOD) %= MOD;
119 }
120 dp[i][j] = R * (p[j] * inv100 % MOD) % MOD * qpow((1 - P + MOD) % MOD, MOD - 2) % MOD;
121 }
122 }
123 Matrix base(24, 3);
124 (ans * qpow(base, N)).SetAns();
125 printf("%lld\n", ansv);
126 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
127 return 0;
128}
129
130template < typename T >
131inline T read(void){
132 T ret(0);
133 int flag(1);
134 char c = getchar();
135 while(c != '-' && !isdigit(c))c = getchar();
136 if(c == '-')flag = -1, c = getchar();
137 while(isdigit(c)){
138 ret *= 10;
139 ret += int(c - '0');
140 c = getchar();
141 }
142 ret *= flag;
143 return ret;
144}
给定终点 -1
。
首先这道题应该很明显是分类讨论,但是找到的性质的多少也就决定了式子最终的复杂程度。
首先这八个向量分别对应了右、右上、上、
首先我们想到,若终点可以被一个向量表示,那么一定可以只用这个向量表示(废话)。
其次一个显而易见的性质,显然两个相邻的四向向量可以表示出其夹着的八向向量(但贡献会多
所以不难想到,如果一个向量可以被任意两个向量表示,那么就变成了一个简单的解方程的问题,而若解出来的解全都不合法(有负数或者不为整数),就说明这个向量无法被仅用两个向量表示。
而这里我们可以思考一下,对于某个象限内的终点,若我们可以用其对应的两个四向向量,那么是一定可以表示出来的,所以无法表示就说明我们一定不是有对应的两个四向向量的情况。
而如果是选择的一个四向向量和一个八向向量,那么我们再选一个四向向量上去是没意义的,因为都可以更优地被之前的一个四向向量和一个八向向量表示,所以我们可以考虑一下再选一个八向向量的情况,这个时候我们发现,若这个四向向量用了达到两次,那么就可以在不增加贡献的情况下用另外两个八向向量表示,所以对于这个情况我们可以转化为使用一个四向向量后再用另外两个八向向量解方程。
而对于初始选择两个八向向量在选择一个四向向量的情况与上一种情况本质相同。
同时我们继续思考就会发现再没有更多情况了。
于是我们现在梳理一下共有哪些可能:
令种类数
Tips:上文很多部分的再选一个等语言可能已经默认了额外选择的是相邻的或夹着的,因为其它部分情况的错误性过于显然,故不赘述了。
xxxxxxxxxx
991
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25
26template < typename T = int >
27inline T read(void);
28
29ll A, B;
30ll ans(INFLL);
31ll dx[10] = {0, 1, 1, 0, -1, -1, -1, 0, 1};
32ll dy[10] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
33bitset < 10 > exists;
34
35bool isInteger(ld v){
36 return fabs(ld(ll(v)) - v) < EPS;
37}
38void Check(int i, int j, int base = 0){
39 if(dx[i] * dy[j] - dx[j] * dy[i] == 0)return;
40 ld v1 = (ld)(B * dx[i] - A * dy[i]) / (dx[i] * dy[j] - dx[j] * dy[i]);
41 if(v1 <= -EPS || !isInteger(v1))return;
42 ld v2 = (ld)(B * dx[j] - A * dy[j]) / (dx[j] * dy[i] - dx[i] * dy[j]);
43 if(v2 <= -EPS || !isInteger(v2))return;
44 ans = min(ans, ll(v1) + ll(v2) + base);
45}
46
47int main(){
48 // freopen("in.txt", "r", stdin);
49 // freopen("out.txt", "w", stdout);
50 int T = read();
51 while(T--){
52 A = read(), B = read();
53 for(int i = 1; i <= 8; ++i){
54 char c = getchar(); while(!isdigit(c))c = getchar();
55 exists[i] = c == '1';
56 }ans = INFLL;
57 if(!A && !B){printf("0\n"); continue;}
58 for(int i = 1; i <= 8; ++i)
59 if(exists[i]){
60 if(A * dx[i] < 0 || B * dy[i] < 0)continue;
61 if((!dx[i] && (A || !isInteger((ld)B / dy[i]))) || (!dy[i] && (B || !isInteger((ld)A / dx[i]))))continue;
62 if(!dx[i])ans = min(ans, B / dy[i]);
63 if(!dy[i])ans = min(ans, A / dx[i]);
64 ld v1 = (ld)A / dx[i], v2 = (ld)B / dy[i];
65 if(!isInteger(v1) || !isInteger(v2) || (ll)v1 != (ll)v2)continue;
66 ans = min(ans, (ll)v1);
67 }
68 for(int i = 1; i <= 8; ++i)for(int j = i + 1; j <= 8; ++j)
69 if(exists[i] && exists[j])Check(i, j);
70 for(int i = 2; i <= 8; i += 2){
71 if(!exists[i] || !exists[i == 2 ? 8 : i - 2])continue;
72 for(int j = 1; j <= 8; j += 2){
73 if(!exists[j])continue;
74 A -= dx[j], B -= dy[j];
75 Check(i == 2 ? 8 : i - 2, i, 1);
76 A += dx[j], B += dy[j];
77 }
78 }
79 printf("%lld\n", ans == INFLL ? -1ll : ans);
80 }
81 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
82 return 0;
83}
84
85template < typename T >
86inline T read(void){
87 T ret(0);
88 int flag(1);
89 char c = getchar();
90 while(c != '-' && !isdigit(c))c = getchar();
91 if(c == '-')flag = -1, c = getchar();
92 while(isdigit(c)){
93 ret *= 10;
94 ret += int(c - '0');
95 c = getchar();
96 }
97 ret *= flag;
98 return ret;
99}
update-2023_02_09 初稿