Preface
好久没训练了，一想到现在的水平下周要去打 CCPC Final，感觉冲击 Ag 都成问题啊
这场直接头等战犯，先是开局签到 A 连 WA 四发搞崩罚时，后期模拟 E 怒写半天最后还因为 Corner Case 没过
最后把理论 6 题希望冲 Au 的局打崩了，直接俯冲 Cu 区
A. Hitoshizuku
考虑从小到大考虑每个 \(b_i\) 最小的人，显然让他去匹配两个 \(a_j\le b_i\) 且 \(b_j\) 最小的两个人一定最优
实现的时候最好直接搞几个 set 来维护，我赛时写的双指针有一些奇怪的细节要注意，WA 了好多发
#include
#include
#include
#include
#include
#include
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,vis[N]; array
int main()
{
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n); n*=3;
for (RI i=1;i<=n;++i)
{
int x,y; scanf("%d%d",&x,&y);
a[i]={x,y,i}; b[i]={y,x,i}; vis[i]=0;
}
sort(a+1,a+n+1); sort(b+1,b+n+1);
bool flag=1; RI pa=1,pb=1,cnt=0;
set
vector
while (cnt { while (pb<=n&&vis[b[pb][2]]) ++pb; if (pb>n) { flag=0; break; } vis[b[pb][2]]=1; while (pa<=n&&a[pa][0]<=b[pb][0]) { if (vis[a[pa][2]]) { ++pa; continue; } st.insert({a[pa][1],a[pa][0],a[pa][2]}); ++pa; } int num=0,x,y; while (!st.empty()) { int id=(*st.begin())[2]; st.erase(st.begin()); if (vis[id]) continue; ++num; if (num==1) x=id; else if (num==2) { y=id; break; } } if (num!=2) { flag=0; break; } vis[x]=vis[y]=1; ans.push_back({b[pb][2],x,y}); ++cnt; } if (!flag) { puts("No"); continue; } puts("Yes"); for (auto [x,y,z]:ans) printf("%d %d %d\n",x,y,z); } return 0; } E. Corrupted Scoreboard Log 只能说太久不写代码是这样的，曾经手拿把掐的模拟题现在写的磕磕绊绊，最后还没判 00 的 Corner Case 这题本身没啥思维难度，把整个串分解后，考虑枚举第一题和前面的分界符 剩下每题直接分类讨论一下各种情况即可，注意到每个题的提交次数只有 \(1/2/3\) 位，三位的情况又很特殊可以直接判，因此这部分复杂度是 \(O(2^m)\) 的 #include #include #include #include #define RI register int #define CI const int& using namespace std; int n,m; string ans; vector inline void DFS(CI tot_pro,CI tot_pnt,string ans,CI pro,CI pnt,CI now) { // if (tot_pnt==1322&&now // if (tot_pnt==1322) printf("now = %d,tot_pro = %d, tot_pnt = %d , pro = %d, pnt = %d\n",now,tot_pro,tot_pnt,pro,pnt); if (now==vec.size()) { if (pro==tot_pro&&pnt==tot_pnt) { cout< } return; } string tmp_ans=ans; if (tp[now]==1) // try case { if (vec[now]=="1") { ans+=" 1 try"; DFS(tot_pro,tot_pnt,ans,pro,pnt,now+1); ans=tmp_ans; return; } int cur_pnt=0; for (RI j=0;j cur_pnt=cur_pnt*10+vec[now][j]-'0'; if (vec[now][0]=='0') { if (cur_pnt==0&&vec[now].size()==2) { ans+=' '; for (RI j=0;j ans+=' '; ans+=vec[now].back(); ans+=" try"; DFS(tot_pro,tot_pnt,ans,pro+1,pnt+cur_pnt,now+1); ans=tmp_ans; } return; } if (cur_pnt>299) return; ans+=' '; for (RI j=0;j ans+=' '; ans+=vec[now].back(); ans+=" try"; DFS(tot_pro,tot_pnt,ans,pro+1,pnt+cur_pnt,now+1); ans=tmp_ans; return; } if (vec[now][0]!='0') //do not solve this problem { int try_times=0; for (RI j=0;j try_times=try_times*10+vec[now][j]-'0'; if (try_times<=100) { ans+=' '; for (RI j=0;j ans+=" tries"; DFS(tot_pro,tot_pnt,ans,pro,pnt,now+1); ans=tmp_ans; } } if (flag) return; if (vec[now].size()>=2&&vec[now].back()!='0'&&vec[now].back()!='1') //1 digit { int cur_pnt=0; for (RI j=0;j cur_pnt=cur_pnt*10+vec[now][j]-'0'; if (vec[now][0]=='0') { if (cur_pnt==0&&vec[now].size()==2) { ans+=' '; for (RI j=0;j ans+=' '; ans+=vec[now].back(); ans+=" tries"; DFS(tot_pro,tot_pnt,ans,pro+1,pnt+cur_pnt+(vec[now].back()-'0'-1)*20,now+1); ans=tmp_ans; } } else if (cur_pnt<=299) { ans+=' '; for (RI j=0;j ans+=' '; ans+=vec[now].back(); ans+=" tries"; DFS(tot_pro,tot_pnt,ans,pro+1,pnt+cur_pnt+(vec[now].back()-'0'-1)*20,now+1); ans=tmp_ans; } } if (flag) return; if (vec[now].size()>=3&&vec[now][vec[now].size()-2]!='0') //2 digits { int cur_pnt=0; for (RI j=0;j cur_pnt=cur_pnt*10+vec[now][j]-'0'; int try_times=0; for (RI j=vec[now].size()-2;j try_times=try_times*10+vec[now][j]-'0'; if (vec[now][0]=='0') { if (cur_pnt==0&&vec[now].size()==3) { ans+=' '; for (RI j=0;j ans+=' '; for (RI j=vec[now].size()-2;j ans+=" tries"; DFS(tot_pro,tot_pnt,ans,pro+1,pnt+cur_pnt+(try_times-1)*20,now+1); ans=tmp_ans; } } else if (cur_pnt<=299) { ans+=' '; for (RI j=0;j ans+=' '; for (RI j=vec[now].size()-2;j ans+=" tries"; DFS(tot_pro,tot_pnt,ans,pro+1,pnt+cur_pnt+(try_times-1)*20,now+1); ans=tmp_ans; } } if (flag) return; if (vec[now].size()>=4&&vec[now][vec[now].size()-3]=='1'&&vec[now][vec[now].size()-2]=='0'&&vec[now].back()=='0') // 3 digits (only 100) { int cur_pnt=0; for (RI j=0;j cur_pnt=cur_pnt*10+vec[now][j]-'0'; if (vec[now][0]=='0') { if (cur_pnt==0&&vec[now].size()==4) { ans+=' '; for (RI j=0;j ans+=' '; ans+="100 tries"; DFS(tot_pro,tot_pnt,ans,pro+1,pnt+cur_pnt+(100-1)*20,now+1); ans=tmp_ans; } } else if (cur_pnt<=299) { ans+=' '; for (RI j=0;j ans+=' '; ans+="100 tries"; DFS(tot_pro,tot_pnt,ans,pro+1,pnt+cur_pnt+(100-1)*20,now+1); ans=tmp_ans; } } if (flag) return; } inline void solve(CI tot_pro) { // printf("tot_pro = %d\n",tot_pro); for (RI i=1;i<=6;++i) { string tmp_ans=ans; if (i>=vec[0].size()) break; string tmp=vec[0]; // cout<<"tmp = "< int tot_pnt=0; for (RI j=0;j tot_pnt=tot_pnt*10+tmp[j]-'0'; if (tmp[0]=='0') { if (tmp.size()-i!=1) continue; } vec[0]=""; for (RI j=tmp.size()-i;j vec[0]+=tmp[j]; for (RI j=0;j // cout<<"i = "< DFS(tot_pro,tot_pnt,ans,0,0,0); if (flag) return; vec[0]=tmp; ans=tmp_ans; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for (RI id=1;id<=n;++id) { vec.clear(); tp.clear(); flag=0; string s; cin>>s; string tmp=""; if (s=="00") { cout<<"0 0"< for (RI i=0;i { if (s[i]=='t') { vec.push_back(tmp); tmp=""; if (s[i+2]=='y') tp.push_back(1),i+=2; else tp.push_back(0),i+=4; continue; } tmp+=s[i]; } int d=vec[0][0]-'0'; vec[0].erase(vec[0].begin()); ans=""; ans+=char(d+'0'); ans+=' '; solve(d); if (flag) continue; int dd=vec[0][0]-'0'; vec[0].erase(vec[0].begin()); ans=""; ans+=char(d+'0'); ans+=char(dd+'0'); ans+=' '; solve(d*10+dd); } return 0; } F. Boolean Function Reconstruction 被徐神单切力 考虑一种很 trivial 的构造方式，对于所有 \(f(i)=1\) 的状态 \(i\)，直接把它对应的与表达式或到最后的答案中即可 更进一步的观察，我们可以发现由于序列中没有取反，因此如果状态 \(f(x)=1\)，那么 \(x\) 的所有超集 \(y\) 都满足 \(f(y)=1\)，因此可以贪心地构造最小的那些表示状态 但如果直接这么做还是会超过符号限制，因此我们不妨合并一些子项，即按顺序提取出每一个字符，再将剩下的子项按照含有/不含有这个字符分类，递归构造即可 #include namespace check { using bitset = std::bitset<1 << 15>; bitset val[15]; bitset eval(const char *&s) { if(isalpha(*s)) return val[*s++ - 'a']; assert(*s == '('); auto val1 = eval(++s); const char *p1 = s; auto val2 = eval(++s); assert(*s++ == ')'); if(*p1 == '&') return val1 & val2; else return val1 | val2; } std::string check(int n, std::string s) { for(int i = 0; i < n; ++i) for(int j = 0; j < (1 << n); ++j) val[i][j] = (j >> i & 1); const char *p = s.c_str(); auto result = eval(p); std::stringstream res; for(int i = 0; i < (1 << n); ++i) res << result[i]; return res.str(); } } void generate(int i, const std::vector std::vector int aa = 0; for(auto s: s) { if(s >> i & 1) { if(s == (1 << i)) aa = 1; else a.push_back(s ^ (1 << i)); } else b.push_back(s); } if((a.size() || aa) && b.size()) ss << '('; if(a.size()) ss << '('; if(aa || a.size()) ss << char(i + 'a'); if(a.size()) ss << '&', generate(i + 1, a, ss), ss << ')'; if((a.size() || aa) && b.size()) ss << '|'; if(b.size()) generate(i + 1, b, ss); if((a.size() || aa) && b.size()) ss << ')'; return ; } void work() { int n; std::cin >> n; std::string input; std::vector std::cin >> input; for(int i = 0; i < (1 << n); ++i) c[i] = (input[i] == '1'); } int op_count = 0; int count0 = 0; for(int i = 0; i < (1 << n); ++i) count0 += (c[i] == 0); if(count0 == 0 ) return std::cout << "Yes\nT\n", void(0); if(count0 == (1 << n)) return std::cout << "Yes\nF\n", void(0); if(c[0] == 1) return std::cout << "No\n", void(0); std::vector std::vector for(int i = 1; i < (1 << n); ++i) { if(d[i] && !c[i]) return std::cout << "No\n", void(0); if(d[i] == c[i]) continue; ans.push_back(i); for(int S = ((1 << n) - 1) ^ i; ; S = (((1 << n) - 1) ^ i) & (S - 1)) { d[S | i] = 1; if(S == 0) break; } } std::cout << "Yes\n"; std::stringstream anss; generate(0, ans, anss); std::cout << anss.str() << char(10); return ; } int main() { // freopen("data.in", "r", stdin); // freopen("data.out", "w", stdout); std::ios::sync_with_stdio(false); int T; std::cin >> T; while(T--) work(); fclose(stdin); return 0; } G. Collatz Conjecture 首先注意到 \([1,B]\) 中的所有数都一定在某个环上 这是因为对于某个 \(x\in [1,B]\)，它在加上了若干次 \(B\) 并成为 \(y\times A\) 后，除去 \(A\) 变为的 \(y\) 一定也 \(\in[1,B]\) 不妨假设初始的 \(n\) 在环上，则它一定由某个 \(r\in[1,B]\) 不断加 \(B\) 得来，很容易发现这个 \(r\) 和 \(n\) 模 \(B\) 意义下同余 定下 \(r\) 后判断 \(n\) 是否合法只要找出环上最大的值即可，设进行了 \(x\) 次加 \(B\) 操作，则有 \(r+x\times B=y\times A\)，用 exgcd 解出最小的 \(x\) 即可 #include using namespace std; #define int long long int ex_gcd(int a, int b, int &x, int &y) { if (0 == b) {x = 1; y = 0; return a;} int ret = ex_gcd(b, a%b, y, x); y -= a / b * x; return ret; } int calc(int A, int B, int R) { //xA + yB = R 的最小正整数 x int x0, y0; int g = ex_gcd(A, B, x0, y0); int x00 = x0 * (R / g), y00 = y0 * (R / g); int x1 = B / g, y1 = A / g; return ((x00 % x1) + x1) % x1; } bool solve() { int A, B, n; cin >> A >> B >> n; int r = n % B; if (0 == r) r = B; int x = calc(B, A, -r); // printf("x = %d\n", x); int n0 = r + x * B; return n <= n0; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) cout << (solve() ? "Yes\n" : "No\n"); return 0; } H. Staircase Museum 我写 E 的时候队友把这题讨论出来了，但后面因为时间原因也没写完 赛后看了下队友的写法好像和官方题解不太一样，感觉很神奇 #include using namespace std; const int INF = (int)1e9+5; #define ft first #define sd second const int N = 2e6+50; int l[N], r[N], yyy[4][N], dp[N], deg[N]; vector vector map struct Node { int x, y, typ; }; vector // int allocate(pair // if (!id.count(pr)) id[pr] = ++cntid; // return id[pr]; // } int getdist() { vector for (int i=0; i<=cntid; ++i) { if (deg[i]==0) que2.push_back(i), ++ed2; } while (fr2 <= ed2) { int x = que2[fr2++]; // printf("x=%d fr2=%d ed2=%d\n", x, fr2, ed2); for (int v : G[x]) if (deg[v]>0){ // printf("v=%d\n", v); dp[v] = max(dp[v], dp[x]+1); --deg[v]; if (0 == deg[v]) que2.push_back(v), ++ed2; } } return dp[0]; } int solve() { int n; cin >> n; for (int i=1; i<=n; ++i) cin >> l[i] >> r[i]; for (int i=0; i<=n; ++i) { if (i+1 <= n) yyy[0][i] = r[i+1]; else yyy[0][i] = INF; if (i > 0) yyy[1][i] = r[i]; else yyy[1][i] = r[1]; if (i+1 <= n) yyy[2][i] = l[i+1]-1; else yyy[0][i] = INF; if (i > 0) yyy[3][i] = l[i]-1; else yyy[3][i] = l[1]; } ul.push_back(-1); dr.push_back(-1); ul.push_back(0); for (int i=1; i if (yyy[0][i] != yyy[0][i-1]) ul.push_back(i); } for (int i=1; i if (yyy[3][i] != yyy[3][i+1]) dr.push_back(i); } dr.push_back(n); auto pr1 = make_pair(ul.back(), yyy[0][ul.back()]); // printf("ul:(%d %d)\n", ul.back(), yyy[0][ul.back()]); que.push_back(Node{pr1.ft, pr1.sd, 0}); ++ed; id[pr1] = ++cntid; dp[cntid] = 0; auto pr2 = make_pair(dr.back(), yyy[3][dr.back()]); // printf("dr:(%d %d)\n", dr.back(), yyy[3][dr.back()]); que.push_back(Node{pr2.ft, pr2.sd, 1}); ++ed; id[pr2] = ++cntid; dp[cntid] = 0; while (fr <= ed) { auto [x, y, typ] = que[fr++]; int cur = id[make_pair(x, y)]; // printf("x=%d y=%d typ=%d\n", x, y, typ); if (0 == typ) { if (x > 0) { int x1 = x; int y1 = yyy[3][x]; int tmpid; if (!id.count({x1, y1})) { que.push_back(Node{x1, y1, 1}); ++ed; id[{x1, y1}] = ++cntid; tmpid = cntid; } else { tmpid = id[{x1, y1}]; } G[cur].push_back(tmpid); ++deg[tmpid]; } else { G[cur].push_back(0); ++deg[0]; } int x0 = *prev(lower_bound(ul.begin(), ul.end(), x)); // printf("x0=%d\n", x0); if (x0 > -1) { int y0 = yyy[0][x0]; int tmpid; if (!id.count({x0, y0})) { que.push_back(Node{x0, y0, 0}); ++ed; id[{x0, y0}] = ++cntid; tmpid = cntid; } else { tmpid = id[{x0, y0}]; } G[cur].push_back(tmpid); ++deg[tmpid]; } } else { if (y > l[1]-1) { int x0 = lower_bound(yyy[0], yyy[0]+n+1, y) - yyy[0]; int y0 = y; int tmpid; if (!id.count({x0, y0})) { que.push_back(Node{x0, y0, 0}); ++ed; id[{x0, y0}] = ++cntid; tmpid = cntid; } else { tmpid = id[{x0, y0}]; } G[cur].push_back(tmpid); ++deg[tmpid]; } else { G[cur].push_back(0); ++deg[0]; } int x1 = *prev(lower_bound(dr.begin(), dr.end(), x)); if (x1 > -1) { int y1 = yyy[3][x1]; int tmpid; if (!id.count({x1, y1})) { que.push_back(Node{x1, y1, 1}); ++ed; id[{x1, y1}] = ++cntid; tmpid = cntid; } else { tmpid = id[{x1, y1}]; } G[cur].push_back(tmpid); ++deg[tmpid]; } } } // for (int i=1; i<=cntid; ++i) { // for (int v : G[i]) { // dp[v] = max(dp[v], dp[i]+1); // } // } int ans = getdist(); // printf("y1:"); for (int i=0; i<=n; ++i) printf("%d ", yyy[1][i]); puts(""); // for (auto [pri, idd] : id) { // printf("(%d %d) %d\n", pri.ft, pri.sd, idd); // } // for (int i=1; i<=cntid; ++i) { // printf("%d:", i); // for (int v : G[i]) { // printf("%d ", v); // }puts(""); // } // printf("dp:"); for (int i=0; i<=cntid; ++i) printf("%d ", dp[i]); puts(""); for (int i=0; i<=cntid; ++i) { dp[i] = -1; deg[i] = 0; G[i].clear(); } ul.clear(); dr.clear(); id.clear(); cntid = 0; ed = -1, fr = 0; que.clear(); return ans; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) cout << solve() << '\n'; return 0; } I. Color-Balanced Tree 应该也是个签到构造，我题目都没看 #include using namespace std; const int N = 2e5+5; int n, col[N], cnt[2]; int ed=-1, fr=0, que[N]; vector void solve() { cin >> n; ed = -1, fr = 0; cnt[0] = cnt[1] = 0; for (int i=1; i<=2*n; ++i) { col[i] = -1; G[i].clear(); } for (int i=1; i<2*n; ++i) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } col[1] = 1; ++cnt[1]; que[++ed] = 1; while (fr<=ed) { int x = que[fr++]; bool isleaf = true; for (int v : G[x]) if (-1 == col[v]) { col[v] = col[x]^1; ++cnt[col[v]]; que[++ed] = v; isleaf = false; } if (isleaf) { --cnt[col[x]]; col[x] = -1; } } // printf("n=%d\n", n); for (int i=1; i<=2*n; ++i) { if (-1==col[i]) { if (cnt[0] <= cnt[1]) { ++cnt[0]; col[i] = 0; } else { ++cnt[1]; col[i] = 1; } } cout << col[i] << (i==2*n ? '\n' : ' '); } } Postscript 五一训练保三争四吧，不然现在的水平和状态包去被薄纱的
亚美尼亚国家足球队