ACgame
一个简单的小游戏
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 尔玉！
相关推荐
2023-02-18
1230. K倍区间
1230. K倍区间原题链接 思路前缀和应用正常想法O（n^2）求前缀和后根据端点遍历另一个端点。 想到求余数（性质）可优化到O（n）前缀和是a1ai的和，那么a？ ~ ai的和的余数为0只要a1a？的余数等于a？ ~ai的余数即可。 所以用一个新数组存前缀和余数，然后直接根据判断满足的个数即可。 相当于优化掉了根据端点遍历另一个端点的时间。注意LL问题（a[i]要用LL，我这里%k了可以不用）代码1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int n, k;int a[N], c[N];int main(){ cin >> n >> k; for(int i = 1; i <= n; i ++) { cin >> a[i]; a[i] = (a[i] + a[i - 1]) % k; }...
2023-02-15
3956. 截断数组
3956.截断数组原题链接 思路截两段，三数组各元素和相等。 求截断方法数。 判断特殊情况 输入时求总数sum，sum不是3的倍数直接输出0结束。 sum为0时，公式求解。 记得long long。 前缀和求a[1] ~ a[i]是多少，求等于sum/3和sum/3*2的个数 从头到尾求方案数 事件复杂度：O(n) 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int a[N];int main(){ int n; cin >> n; int sum = 0; for(int i = 1; i <= n; i ++) { cin >> a[i]...
2023-04-04
4275. Dijkstra序列
4275.Dijkstra序列原题链接 思路Dijkstra板子改改（内部判断一下能否实现即可） 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include<bits/stdc++.h>using namespace std;const int N = 1010;int g[N][N];int dist[N];bool st[N];int fl[N];int n,m,k;bool dj(){ memset(dist, 0x3f, sizeof dist); //这里st忘了复原了，所以我当时出错。 memset(st, 0, sizeof st); dist[fl[1]] = 0; for(int t = 1; t <= n; t ++) { // 我的写法 int ...
2022-03-02
95.费解的开关
95.费解的开关AcWing 95. 费解的开关 你玩过“拉灯”游戏吗？ 25盏灯排成一个 5×5的方形。 每一个灯都有一个开关，游戏者可以改变它的状态。 每一步，游戏者可以改变某一个灯的状态。 游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字 1表示一盏开着的灯，用数字 0表示关着的灯。 下面这种状态 123451011101101101111000011011 在改变了最左上角的灯的状态后将变成： 123450111111101101111000011011 再改变它正中间的灯后状态将变成： 123450111111001110011010011011 给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6步以内使所有的灯都变亮。 输入格式第一行输入正整数 n，代表数据中共有 n个待解决的游戏初始状态。 以下若干行数据分为 n组，每组数据有 5 行，每行 5个字符。 每组数据描述了一个游戏的初始状态。 各组数据间用一个空行分隔。 输出格式一共输出 n行数据，每行有一个小于等于 6的整数，它表示对于输入数据中对应的游戏状态...
2023-03-30
3777. 砖块（每日一题）
AcWing 3777. 砖块（每日一题）原题链接 思路1.审题：判断出当B砖和W砖都为奇数个时不成立每次翻转会使两个砖变为另一种颜色或两个砖交换颜色。所以颜色都为奇数个时将无法翻转成同一种颜色。 2.暴力 + 判暴力复杂度思路：分别判断全为B或全为W时需要多少步。 方法： 从左到右==-1个==判断是否为需要颜色，不是就翻一下它和它后面的（-1的由来）。 判断最后一个和前面颜色是否相同，不同则选择另一个（下题解将此总数+1e7保证选到另一个） 时间复杂度：O（nt）（t组数，n操作数） 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include<bits/stdc++.h>using namespace std;const int N = 210;int n,m;string s,cp;int num1...
2021-09-11
STL
STL简记