SDNU-ACM2022.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的范围很大，1e12数组开不下，所以我开了三个1e6的数组妄图使1e6+1e6=1e12。（虽然真的很好笑但是当时我re到崩溃了）。

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

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

#includeusing 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很板，不如师哥灵活。

#includeusing 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;
vectorarr[N];
bool vis[N];
bool exi[100005];
vectorent;

struct node {
	int now;
	int cnt;
};

void bfs() {
	queueq;
	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。

#includeusing 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字串的理论形态应该是全为最后一个字符的。

#includeusing 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也有人歪榜啊那能怎么办，不能把自己的节奏押在别人身上。自己乱开题还死磕就是能力的缺失啊靠。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧