这场UI还有红色特效
https://atcoder.jp/contests/abc227/tasks
D - Project Planning
长n数组a
每次选k个不同的下标, 让值减1,(保证所有值非负), 求多减的次数
范围
n 2e5
ai [1..1e12]
2s
1024mb
我的思路
感觉如果数据量小,每次最大k个下标减1
但这样每次要排序, 而且ai很大
题解
对答案考虑, 是否能做p次
s = sum min(ai,p)
如果 kp > s, 显然不可能, 因为左边是需要的个数, 右边是’可能’的上界
然后就是精彩的 可以数学证明 如果 kp <= s 则一定可以
如果有多于k个 ai >= p, 那么就指定其中k个 然后做p次即可
否则, 选择最大的k个做1次, 那么 kp <= s 不等式 左边相当于-k, 右边最多减k
因此 不等式依然成立, 而变成子问题就是归纳法了
得证
代码
https://atcoder.jp/contests/abc227/submissions/34432305
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
ll a[200010];
int main(){
int n = read();
int k = read();
rep(i,0,n) a[i] = read();
ll l = 0, r = 1e18 / k;
while(l + 1 < r){
ll mid = (l + r) / 2;
ll s = 0;
rep(i,0,n) s += min(a[i], mid);
(s >= k * mid ? l : r) = mid;
}
printf("%lld\n",l);
return 0;
}
|
E - Swap
只包含KEY3种字符的字符串, 问 <= k次相邻交换能产生多少种字符串
范围
len < 30
k [0..10^9]
我的思路
k 最多30+29+28+… < 500次 能得到所有字符
然后字符串种树并不是3的30次方
而是假设最开始 a,b,30-a-b 个的排列方式
30 !/ ( a! b! (30-a-b) !)
依然很大可能达到 > 10^12 次方量级
考虑
dp[i][k][e][<=op]
30*30*30*500
但不太知道如何转移
题解
考虑说如果给定S,T 如何求最小交换次数, 显然 按位置就近移动
dp[i][x][e][y] = 长度为i的字符串T, e个E,y个Y, at least x 次操作, 让S[0..i] 变成T的方案数
ti指定的话, 它的来源一定是剩余s中 同个字符的第一个
这样就可以转移了
而且注意到, 当前i个指定e和y的个数后,k的个数也是确定的, 而相当于对s 去掉了最前的e个E,y个Y和k个K, 所以剩余的s的内容是唯一的!!!
剩下就是实现了
代码
https://atcoder.jp/contests/abc227/submissions/34432995
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
char s[100];
unordered_map<int,unordered_map<int,unordered_map<int,pair<string,ll>>>> dp;
int main(){
scanf("%s",s);
int n = strlen(s);
int k = read();
dp[0][0][0] = {s,1};
rep(_,0,n){
unordered_map<int,unordered_map<int,unordered_map<int,pair<string,ll>>>> ndp;
for(auto [x,d1]:dp) for(auto [e,d2]:d1) for(auto [y,sv]:d2) {
auto [s0,c] = sv;
for(auto ch: {'K','E','Y'}) rep(idx,0,s0.size()) if(ch == s0[idx]){
int x1 = x+idx;
int e1 = e+(ch == 'E');
int y1 = y+(ch == 'Y');
string s1 = s0.substr(0,idx) + s0.substr(idx+1);
if(!ndp[x1][e1].count(y1)) ndp[x1][e1][y1] = {s1, 0};
ndp[x1][e1][y1].second += c;
break;
}
}
dp = ndp;
}
ll ans = 0;
for(auto [x,d1]:dp) if(x <= k) for(auto [e,d2]:d1) for(auto [y,sv]:d2) ans += sv.second;
printf("%lld\n",ans);
return 0;
}
|
F - Treasure Hunting
h * w 的矩阵, 左上走到右下, 只能向下或向右
问 路径中最大的K个数字的和最小值
范围
h,w 30
aij [1,1e9]
我的思路
想从两端做meet in middle, 但是 一半也有2的30次方
记录从开始 到当前位置的maxk 最小的
但是并没有局部性
例如两条路径分别是
显然后面的会更小, 但是如果未来接了更多大的, 就会更大
并没有局部性
题解
固定第k大是矩阵中的哪一个,来做, 令其为x
dp[i][j][>= x的个数] = 路径中大于等于 x的所有值的和 的最小值
这样做的话显然对于指定的x是有局部性的, 因为个数也拆出来了
dp[i][j][c] = min(dp[i-1][j][c-(a[i][j] >= x)],dp[i][j-1][c-(a[i][j] >= x)])
然后
结果就是
dp[h][w][k??], 这里的问题是,当选定x以后, 个数可能无法刚好是k(比如反例所有值都一样的时候)
解决方案是, 这里的c 并不是记录所有>=x 的个数
而是变成选择了的>=x的个数,当然结果还是对应的被选的值的和
但是这里保证的是>x是必选, 而=x 是可选可不选
这样一来,其实是看成x 是当前路径上排序第c大下标的, dp的值是前c大的和
这样一是 依然有局部性, 而又保证了不会出现中间空白的情况, dp的有效的一定是连续的一段
这样的话结果就是 min(dp[h][w][k])
代码
https://atcoder.jp/contests/abc227/submissions/34442116
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
const ll INF = 1e11;
void setmin(ll&a,ll b){if(a>b) a = b;}
int main(){
int h = read();
int w = read();
int k = read();
auto a = vector(h,vector(w,0));
rep(i,0,h) rep(j,0,w) a[i][j] = read();
ll ans = INF;
for(auto row: a) for(auto x : row) {
auto dp = vector(k+1,vector(h,vector(w,INF)));
if(a[0][0] >= x) dp[1][0][0] = a[0][0];
if(a[0][0] <= x) dp[0][0][0] = 0;
rep(c,0,k+1) rep(i,0,h) rep(j,0,w) if(i || j){
if(a[i][j] >= x && c){
setmin(dp[c][i][j], a[i][j] + (i ? dp[c-1][i-1][j] : INF));
setmin(dp[c][i][j], a[i][j] + (j ? dp[c-1][i][j-1] : INF));
}
if(a[i][j] <= x){
setmin(dp[c][i][j], (i ? dp[c ][i-1][j] : INF));
setmin(dp[c][i][j], (j ? dp[c ][i][j-1] : INF));
}
}
setmin(ans, dp[k][h-1][w-1]);
}
printf("%lld\n", ans);
}
|
G - Divisors of Binomial Coefficient
题意如标题,计算binom(n,k) 的因子个数
答案mod998244353
范围
n 1e12
k 1e6
2s
1024mb
我的思路
我掏出了我之前写的 质数判别+质数拆解的板子
想暴力 + map 做
但是sample3我本地就跑了31s, 很久很久
另一个思路是
n/1 (n-1) /2 的顺序算
但还是免不了对大数做分解?
再有就是, 直接去 n-k+1~n里找i的倍数,做除发
问题是对于单个很好找, 但是对于多个来说, 可能两个数都找到同一个导致除法不够除
题解
一样的 , ans = prod(pwr+1)
直接数筛法去 对小的进行质因数分解
对于大的一样类似的暴力!!!!!!, sqrtN个质因子去尝试K个数
因为复杂度依然是 = k/1 + k/2 + k/3 +.. +… k/sqrt(N)
哇! 又是会的知识变形了就不会用了…..
代码
https://atcoder.jp/contests/abc227/submissions/34448377
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
| #include <bits/stdc++.h>
const int MOD = 998244353;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
const int N = 1000000;
const int P = N + 10;
bool pr[P];
ll a[2][N+10];
ll read(){ll r;scanf("%lld",&r);return r;}
int main(){
ll n = read();
ll k = read();
std::fill(pr+2,pr+P,true);
for(ll p=2;p*p < P;p++) if(pr[p]) for(ll i = p*p;i < P;i+=p) pr[i]=false;
ll s[] = {n-k+1,1};
rep(o,0,2) std::iota(a[o],a[o]+k,s[o]);
ll ans = 1;
rep(p,2,P) if(pr[p]){
int power = 0;
rep(o,0,2) for(ll v=((s[o]+(p-1))/p)*p;v<=s[o]+k-1;v+=p) while(a[o][v-s[o]]%p==0){
power+= (const int[]){1,-1}[o];
a[o][v-s[o]] /= p;
}
(ans *= power+1) %= MOD;
}
rep(i,0,k) (ans *= (1+(a[0][i] != 1)))%=MOD;
printf("%lld\n",ans);
}
|
H - Eat Them All
3 x 3的矩阵
上面数字aij
(1,1) 出发, 每次, 当前-1(保证非负), 再四临移动
当所在为0时,终止
现在需要找一个方案消耗所有值并回到(1,1), 输出具体方案
范围
aij [1,100]
2 s
1024 mb
我的思路
看起来向个多重边的欧拉回路?
目前想法是本质上很多个环的叠加, 而每个环自身是每个点至多经过一次
所以 如果有办法,把数拆成多个环的和再把环拼起来就好了
其中有一点特殊的两个点构成的环
2个点 12 种
4个点4种
6个点4种
8个点5种
然后有点像解25元一次线性方程组, 看有没有解, 不过这里行为9行,所以rank不超过9
而且因为这里需要方案合并的关系 还要保证方案中可以重叠构成一个连通的
然后想了一下, 4个6个8个 都是可以 由两个的 组合得到
所以可以变成 12种2个点的 线性方程组
问题就是如果得到的方案可以拼接 那肯定是一种解, 但如果不能拼接 是否有办法转换成另一个线性方程组的解, 来得到有效解?
题解
考虑9点12边的二分图
指定每条边通过的次数
每个点的值和它的出度/入度相等
移除了那些未经过的边, 剩余的还是连通
- 计算边通过的次数
枚举边的选择情况2^{12}种, 做9个点的树(保证连通性),
也就是 如果有方案, 是可以拆成 树的方案+ 剩余做最大流的, 而合并树上和最大流的边代价,再做欧拉回路
确保每条边经过至少一次
然后计算最大流
- 实际构建一个方案
欧拉回路 = (dfs记录边+逆序)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| vector<int> euler_circuit(vector<vector<pair<int, int>>> G, int n, int m) {
vector<int> path;
vector<bool> used(m, false);
function<void(int)> dfs=[&](int u) {
for(auto [v,e]: G[u]) {
if(!used[e]) {
used[e] = true;
dfs(v);
}
}
path.push_back(u);
};
dfs(0);
reverse(path.begin(), path.end());
return path;
}
|
代码
https://atcoder.jp/contests/abc227/submissions/34449940
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
| #include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
const int N = 3;
const int M = N*N;
const int P = 12;
int a[M];
int c[1<<P];
std::pair<int,int> i2xy(int i){
int x = i<6?i/3+i%3*3:i-6;
int y = i<6?x+1:x+3;
if(x&1) std::swap(x,y);
return {x,y};
}
const int di[] = {0,1,0,-1};
const int dj[] = {1,0,-1,0};
std::pair<int,int> dec(int v){ return {v/N,v%N};}
int enc(int i,int j) { return i*N+j;}
template< class T>
void f(int k, T &e) {
auto [i,j] = dec(k);
rep(l,0,4){
int I=i+di[l];
int J=j+dj[l];
if(I<0||J<0||I>=N||J>=N)continue;
int K = enc(I,J);
int m=std::min(k,K);
m = (l&1) ? m+6 : m/3+m%3*3;
while(e[m].flow){
e[m].flow--;
f(K, e);
printf("%c","LURD"[l]);
}
}
};
int main(){
rep(i,0,M) a[i] = read() * 2;
rep(t,1,1<<P){
c[t] = c[t&(t-1)]+1;
if(c[t] != M-1)continue;
int b[M]={1};
int u[P]={};
atcoder::mf_graph<int>g(M+2);
const int S = M;
const int T = S+1;
rep(i,0,P) {
auto [x,y] = i2xy(i);
g.add_edge(x,y,1000);
}
rep(k,0,M-1) rep(i,0,P){
auto [x,y] = i2xy(i);
if(((t>>i)&1) && !u[i] && b[x]+b[y]) {
u[i]++;
b[x]++;
b[y]++;
}
}
b[0]--;
bool ok = true;
rep(i,0,M) if(!b[i]||b[i]>a[i]) ok = false;
if(!ok)continue;
int x[] = {0,0};
rep(i,0,M){
int d=a[i]-b[i];
if(i&1) g.add_edge(i,T,d);
else g.add_edge(S,i,d);
x[i&1] += d;
}
if(x[0]!=x[1] || g.flow(S,T) != x[0]) continue;
auto e = g.edges();
rep(i,0,P) if(u[i]) e[i].flow++;
f(0,e);
printf("\n");
return 0;
}
printf("NO\n");
return 0;
}
|
总结
D
这1643评分的蓝题也不会啊
看来 还是需要大胆猜测+归纳证明
E
dp的感觉和方向是对的, 但是问题在于说 没有考虑S也是前i项目
然后转移不是把si 插入到前面i-1中,因为这样难处理重复(我的思路方向), 而是说ti指定的话, 它的来源一定是剩余s中这个字符的第一个
并且还会有制定i,e,y后,剩余的是固定的字符串
F
还是dp但是这里是把第k大, 直接先变成大于某个值的个数,(值->个数) 而不是原来的(个数->值)
然后这里是第c大的想法后, 对于>x必选,==x可选可不选,<x必不选, 这样也有局部性
G
emmm 可以说数筛小的值,学了自己也用了无数次了, 对于大的来说, 这样限定了一个范围, 这样想我是真没想到,
感觉需要一个思维陷入一个方向以后跳出来机制
H
感觉算欧拉回路相关的知识点
一个是怎么求
一个是怎么判断
这么说起来 如果有了指定树,先提出一个树的步骤, 那好像解线性方程依然不行, 可能有负解? , 但如果解出就是和树合并上去即可
以及atcoder mf_graph按照顺序加边, 最后还可以取边上的流量
参考
官方题解