SDNU-ACM 2022.12.4结训赛

目录

前言

A. 柳予欣的归来

​思路

回顾

C. 我没有脑子 (确实)

思路

D. 我是杀猪饲料，祝你天天开心

G. A + B Problem

​思路 

K. 逃出虚圈

​思路

L. 为爱发电的Oier

​思路

N. 泷1千0（easy version）

​思路

F. 泷1千0（hard version）

​思路

其他题

总结

前言

“ 心情不好就把音量开到最大。” 

被薄纱了，是甚至签到都没签完的大失败场。很好笑，师哥说有人做了两三题就去玩了，我是认认真真地卡题崩溃罚坐3小时。但其实出5.6题大概不算难，yysy我的理念是能自己看懂题解的就不应该做不对。

队长写过题解了，这篇没什么好看的，主要是我想记录一下失败，还有一些不想写到lls要看的总结里的总结。高中做题就容易钻牛角尖，没想到现在更严重了，挺失望的。放个博客看看我什么时候才能改掉这个坏习惯。

以下代码只是补题，但是没重交，不知道能不能AC，看看思路即可。

------>2022.12.5更新，交了，改改，注释注意点，都A了。

A. 柳予欣的归来

 思路

对于任意素数p，小于p的数是p的完全剩余系， 对于任意a<p，a的逆存在两种情况：1. a逆=a；2. a逆=b。情况2时对于b来说，b逆=a。所以求出来的逆的集合也是p的完全剩余系，求逆的操作=无。等差数列求和+快速幂即可。注意/2的操作要逆元算。

回顾

因为之前被快速幂卡过好几次（具体可见月赛热身赛），所以这次觉得用线性逆元必赢，但是p的范围很大，1e12数组开不下，所以我开了三个1e6的数组妄图使1e6+1e6=1e12。（虽然真的很好笑但是当时我re到崩溃了）。

别太看重某一个知识点，轴劲儿上来了不知道是帮我还是害我。

ps: 我竟然在思维题上被卡死了，那我仅有的一点优势没了啊，我不允许。

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
const ll N = 1e6 + 1;
const ll MOD = 998244353;ll fastpow(ll A, ll B, ll K ) {ll ans = 1;A = A % K;while (B) {if (B % 2 == 1)ans = (ans * A) % K;B /= 2;A = (A * A) % K;}return ans;
}void work() {ll p, m;cin >> p >> m;p %= MOD;ll ans = p * (p - 1) % MOD * fastpow(2, MOD - 2, MOD);cout << fastpow(ans, m, MOD)<<'\n';//xs,第一遍少打个‘CE了
}int main() {io;work();return 0;
}

C. 我没有脑子 (确实)

思路

自己打表300亿记录一下每亿的结果。（这种技巧要会用）

或者  矩阵快速幂。

//这个不想写了，让我摆吧，别管我了。

D. 我是杀猪饲料，祝你天天开心

蛇姐生日快乐！祝她天天开心！

（蛇姐是我这五个小时里唯一的安慰了）

G. A + B Problem

思路 

本来想的是高精度加法+取模，因为没学取模所以一开始没打算做这个题。看题解发现确实是狗题（dbq其实是我基础知识不扎实）。

ull的最大范围就是2^64，所以溢出其实就是取模，我们根本不用管最终取模，只需要让字符串变成ull即可。这里还有个小点：(a×b+c) % p=((a×b) % p+c % p) % p，但是自然溢出真的很省事啥也不用干。

K. 逃出虚圈

思路

捅死我吧我为什么不写bfs啊，真的对自己很无语，能不能别钻牛角尖了。

 我写的bfs很板，不如师哥灵活。

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define mem(a,b) memset(a,b,sizeof a)
typedef long long ll;
const int N = 1e5 + 5;
vector<int> arr[N];
bool vis[N];
bool exi[100005];
vector<int>ent;struct node {int now;int cnt;
};void bfs() {queue<node>q;for (int i = 0; i < ent.size(); ++i) {node st;st.now = ent[i];st.cnt = 0;q.push(st);}while (!q.empty()) {node cur = q.front();q.pop();if (exi[cur.now]) {cout << cur.cnt << '\n';return;}for (int i = 0; i < arr[cur.now].size(); ++i) {if (!vis[arr[cur.now][i]]) {vis[arr[cur.now][i]] = 1;node tt;tt.cnt = cur.cnt + 1;tt.now = arr[cur.now][i];q.push(tt);}}}cout << "N0\n";//这个大概是输出的坑
}int main() {io;int n, m;mem(exi, 0);mem(vis, 0);cin >> n >> m;while (m--) {int u, v;cin >> u >> v;arr[u].push_back(v);arr[v].push_back(u);}int p, q;cin >> p >> q;while (p--) {int x;cin >> x;ent.push_back(x);}while (q--) {int x;cin >> x;exi[x] = 1;}bfs();return 0;
}

L. 为爱发电的Oier

 思路

这么签的题，我被期望劝退了，6。

E(x)=1/2 * x =n，求x。很好笑，我当时觉得我不会。

N. 泷1千0（easy version）

 思路

无论是取反还是翻转，只要是偶数次操作就相当于无，那么希望修改第i个字符的操作就是进行三步操作：i -> 1 -> i 。通俗来讲就是把i的前缀翻转，此时i位置元素到达1位置，然后修改1，再操作i给他变回去，此时仅i位置的字符进行奇数次操作，其他均进行偶数次操作，即可达到单独修改i的目的。

最坏的情况是对于每一个字符都需要单独修改，此时k=3*n。

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 1005;
int ans[3*N];//这个注意一下，答案是小于3*N的，数组要舍得开
int cnt = 0;int main() {io;string a, b;cin >> a >> b;int n = a.length();for (int i = 0; i < n; ++i) {if (a[i] != b[i]) {ans[++cnt] = i + 1;ans[++cnt] = 1;ans[++cnt] = i + 1;}}cout << cnt;for (int i = 1; i <= cnt; ++i) {cout << " " << ans[i];}cout << '\n';return 0;
}

F. 泷1千0（hard version）

 思路

 修改前缀，我们先让一个字串全为0/1，然后从后往前修改前缀，由于预处理a字串全为0/1，操作中的翻转=无，有点那个完全平方数按灯的感觉（这个理解不了就别理解了我想法很怪）。相当于从后往前找，找到不一样的就把前缀全部改变。

最坏的情况仍然是对于a，b字串，每一个字符都与相邻的不一样且ab互反，预处理和修改都需要n次操作。

可能的注意点：

1. string的下标从0开始，如果能搞清楚就不用管，搞不清楚可以借鉴师哥操作：在前面随便加一个什么字符让下标从1开始。

2. 我们找的now一定是a[n-1]而非a[0]。因为预处理是从前往后的，理论上我们修改了字串，但是实际上我们并没有对字串进行操作，只是记录了答案而已，所以最终a字串的理论形态应该是全为最后一个字符的。

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 100005;
int ans[2*N];//同上int main() {int cnt = 0;string a, b;cin >> a >> b;int n = a.length();for (int i = 1; i < n; ++i) {if (a[i] != a[i - 1]) {ans[++cnt] = i;}}int now = a[n - 1] - '0';for (int i = n - 1; i >= 0; --i) {if (now != (b[i] - '0')) {ans[++cnt] = i + 1;now = 1 - now;//这个是有点妙的}}cout << cnt;for (int i = 1; i <= cnt; ++i) {cout << " " << ans[i];}cout << '\n';return 0;
}

其他题

B. 收收心找个电子厂上班了（编程也就图一乐）

        区间贪心/差分约束。没学，学了再写。

E. 没什么特殊意义，就是想混一个最长的题目名字，然后让大家点进来做这道题

       离散化+ 权值线段树/平衡树/对顶堆/主席树。都不会，学了再写。

H. 柳予欣的色图

        防AK，polya裸题。高中数竞看见过这个，但是只是从 Burnside求不动点 到 旋转/翻转同构的循环节。只有这一部分我是似乎理解的，hqgg给的洛谷题解看了很久但是还是没太理解在群意义下的各种置换，打算等他讲，我不自学了，真学不下去。（yjgg说看我做这题好几个小时，我澄清一下，其实写这题时间真不长，是一直卡A罢了。虽然听起来更蠢）

I. WWW的杂货铺

        谢谢yyjj，真的是简单模拟。

J. 去玩宝可梦喽~

        dp+线段树。先学学dp再说吧。之前听到djk师哥说想出dp，特别简单的。emmm，难以评价。

M. 完全不管大一死活

        谢谢yjgg，出了周赛原题我是没想到的，竟然一点难度都没加？因为没找到蛇姐的题面所以先开了这题，莫名其妙拿了一血。怀念水题时光，年少不知模拟签。

总结

几点反思：

最近打的每一场比赛都在破防，我也不想总是破防啊，显得我很他妈矫情啊，一点都不酷。但难绷也是真难绷，我感觉我现在是除了签到什么也出不来的状态，甚至今天签到都没签完。被吊打，真麻了。

我挺不满意自己现在的状态的，虽然很多次比赛是靠着罚时少名次才没那么难看，但是我写代码实在算不上稳，总是不记得开ll，不注意格式，不想特判等等，我不能保证思路对了就能一次写对；如果说我思维强，今天的思维题也是真的把我卡死了。现在是哪边都不沾，这不应该。

其实最近学的有点用的东西也就一个线段树吧，效率好低，我不想当失败的卷王啊。

舍断离！别钻牛角尖啦，A不了就不想了，死磕一个题真的会让一场比赛都烂掉。yjgg说有队友会好一点，但其实女赛正式赛卡B的时候，姐姐们去写G，我读完了题就又去想B了，中途讨论是有点断层的（很不好意思），幸好是磕出来B了，然后狂补G跟上了思路（虽然最后也是wa的）。那如果没磕出来B呢，其实这样是弊大于利的，这个事还是得改一改的，就看看我什么时候能改掉这个臭毛病吧。

笑死了，yjgg帮我找理由说这次没大二师哥师姐带榜导致我乱开题卡住，安慰一下自己听听得了，不是每一次比赛都会有人带榜，icpc也有人歪榜啊那能怎么办，不能把自己的节奏押在别人身上。自己乱开题还死磕就是能力的缺失啊靠。