WORIA

https://vjudge.net/contest/438452 E - Counting Cliques   题意：给定一张无向图，找出点数等于 S 的团的个数。N ≤ 100,M ≤ 1000,2 ≤ S ≤ 10，每点的度不超过20. 暴力 只存小点到大点的边。从小到大枚举每点，dfs枚举与它相连的点集的子集，判断是否满足条件。 由于点数不超过100，则度为20的点最多有5个，再推下去能发现度为19的点也不超过5个，以此类推，如果枚举点集则最多是 5⋅(220+219+⋯ )=5⋅(221−1)5\cdot(2^{20}+2^{19}+\cdots)=5\cdot(2^{21}-1)5⋅(220+219+⋯)=5⋅(221−1)。每次暴力双重循环判断是否为团，复杂度为 S2/2S^2/2S2/2，则总共为 5⋅221⋅50=5⋅1085\cdot2^{21}\cdot50=5\cdot10^85⋅221⋅50=5⋅108，再稍微剪下枝，当即使后面所有点都选上也不够 S 时，提前结束。 12345678910111213141516171819202122232425262728 ...

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick Start Create a new post 1$ hexo new "My New Post" More info: Writing Run server 1$ hexo server More info: Server Generate static files 1$ hexo generate More info: Generating Deploy to remote sites 1$ hexo deploy More info: Deployment

A. Optimal Currency Exchange   要尽可能多地用掉卢布，而美元以1为单位，欧元以5为单位，所以要n−(a⋅x+b⋅y)n-(a\cdot x+b\cdot y)n−(a⋅x+b⋅y)尽可能小，且x,y为整数，则枚举x,剩余的卢布数为(n−a⋅x)mod  b(n-a\cdot x)\mod b(n−a⋅x)modb 12345678910111213141516171819202122#include<iostream>#include<stdio.h>#include<algorithm>#include<cstring>#include<string>#include<vector>#include<map>#include<queue>using namespace std;#define ll long longtypedef pair<int, int> pii;const int maxn = 2e6 + 5;int n, d, e;int ...

1001 ^ & ^   当a&b不为0时，c=a&b。否则c=a,b中最低一位的1。用x&-x可以直接得到最低位1，当时是队友写的用了循环，也能过。 123456789101112131415161718192021#include <bits/stdc++.h>using namespace std;int main(){ int T; cin >> T; while (T--) { long long a, b; cin >> a >> b; if (a & b) cout << (a & b) << endl; else { int i = 1; while (!(a & i) && !(b & i)) i <<= 1; ...

现场4题，第二天补题时发现hard版本的直接用当时写的easy版代码就能过，结果是当时因为网太卡就没试，感觉亏爆。0.o A. Chips Moving   签到，奇数或偶数内部是等价的，只有在奇偶之间转化时才会+1，因此只要看奇数和偶数哪个个数少。 12345678910111213141516171819202122232425#include<iostream>#include<stdio.h>#include<cstring>#include<string>#include<vector>#include<algorithm>#include<set>#include<cmath>using namespace std;#define ll long longconst int maxn = 1e6 + 5;int n;int c1, c2;int main() { cin.sync_with_stdio(false); cin >> n; for (int i ...

Number theory 素数筛法 扩展欧几里得 gcd A. Submarine in the Rybinsk Sea (easy edition)   全都写下来之后可以看到，就是把每个数字双写，全都相加，再乘以n。 所以主要就是双写，拆分成每一位，乘以11，再乘以相应十的次方。 注意精度 1234567891011121314151617181920212223242526272829303132333435363738394041#include<iostream>#include<stdio.h>#include<cmath>#include<algorithm>#include<cstring>using namespace std;#define ll long longconst ll mod = 998244353;int n;ll ans;ll po[20];void init() { po[0] = 1; for (int i = 1; i < 20; i++) { ...

这是我正规打的第一场比赛啊。！cf神奇的时区导致每次都在半夜开场，这次遇到个八点半的，终于可以试试了。 现场a了三题，终于变绿了，0.o，1500-2，还能接受，其实还能再a一题的，但是由于两个小时六道题真的来不及，所以看到E的时候着急了，看错题了，后来看到题解才反应过来，果断试了一下，虽然还有些波折，但还是过了。   A. Hotelier   签到题 枚举 L就从左开始，R就从右开始枚举 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<iostream>#include<stdio.h>#include<algorithm>#include<cstring>#include <functional>#include<string>#include<set>#include<queue>using namespace std;#define ll long ...

Random Mushup 最近事情比较多（比较懒），所以把三场比赛一起补了，过程可能会简略些。 这场比赛比较迷，两题都是直接枚举过，主要是数学，并查集和dp，图论题没做出来。可能以后还会再补吧 组合数学 贪心，二分 扩展欧几里得 2-sat并查集处理 dp A. Kyoya and Colored Balls   组合数学 每次先确定每种颜色最后一个球的位置，之后该种颜色其他的球就可以在剩下的位置上随便摆放，接着再确定下一种颜色最后一个球的位置，注意，每种颜色最后一个球的位置是确定的，当你已经摆完了所有的4号球后，3号球最后一个只能放在四号球前有空位的最近的地方，所以在求组合数时不能把最后一个球算在内。 123456789101112131415161718192021222324252627282930313233343536373839404142#include<iostream>#include<stdio.h>#include<cmath>#include<algorithm>#include<cstring&g ...

这场数学题似乎比较多，数据结构是模板题，dp题感觉挺难的。 数学，gcd 树链刨分，线段树 dp 数学，几何 Ticket   完全水题，分类讨论即可。 123456789101112131415161718192021222324252627282930#include<iostream>#include<algorithm>#include<vector>#include<cstdio>using namespace std;#define ll long longint n;double sum, ans;int main() { cin >> n; for (int i = 0; i < n; i++) { double a; cin >> a; double b; if (sum < 100) { sum += a; } else if (sum >= 100 && sum < 150) { ...

Binary search,two pinters, meet-in-the-middle, divide-and-conquer Trees 这次真是学到很多新东西，KMP，双指针，点分治，meet in middle等，枚举也是一个技术活，只有正确的枚举才能解决问题。 KMP 前缀和 树上点分治 双指针，二分 并查集 A. Password   KMP模板题 唯一需要注意的是KMP求得的是最大前缀后缀长度，而本题需要任意长度的公共前缀后缀，不过根据KMP的思想，递归next数组就可以了。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<iostream>#include<string>#include<cstring>using namespace std;const int maxn = 1e6 + 5;#define ...