水题笔记_ 星辰大海中闪烁的趣题

写了两天AT的题都不会打代码了…正好srO一番AH吧…

我是不是成弃坑大师了…

捕风捉影

枚举回文+费马小定理判素数

Noip2016之后我总算会枚举回文了…再说一遍枚举半边…题解里怎么都是打表过的啊 怎么就我一个老老实实写的费马小定理啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#define INF (0x7ffffff)
#define MAXN (1000000000 + 5)
#define MOD (1000000000 + 7)
#define LL long long
using namespace std;
int n, m;
vector<LL> ans;
LL ksm(LL, LL, LL);
bool pd(LL);
LL hw(int);
void solve();
int ws(int);
LL mpow(int, int);
int gcd(int a, int b)
{ return (b == 0 ? a : gcd(b, a % b)); }
int main()
{
scanf("%d%d", &n, &m);
solve();
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++)
printf("%lld\n", ans[i]);
return 0;
}
void solve()
{
int begin = mpow(10, ws(n) >> 1);
if (n <= 11 && m >= 11)
ans.push_back(11);
for (; hw(begin) < n; begin++)
{}
for (; hw(begin) <= m; begin++)
{
LL dq = hw(begin);
if (pd(dq))
// printf("%lld\n", dq);
ans.push_back(dq);
}
}
// 123 -> 12321
int ws(int x)
{
int re = 0;
while (x)
x /= 10, ++re;
return re;
}
LL mpow(int x, int y)
{
LL re = 1;
for (int i = 1; i <= y; i++)
re *= x;
return re;
}
LL hw(int x)
{
int wx = ws(x);
LL re = x;
re *= mpow(10, wx - 1);
for (int i = 2; i <= wx; i++)
re += (x / mpow(10, i - 1) % 10) * mpow(10, wx - i);
return re;
}
bool pd(LL x)
{
srand(x ^ rand());
for (int i = 1; i <= 1000; i++)
{
int srx = rand();
while (gcd(srx, x) != 1)
srx = rand();
if (ksm(srx, x - 1, x) != 1)
return false;
}
return true;
}
LL ksm(LL a, LL y, LL mod)
{
if (y == 1)
return a % mod;
if (y == 0)
return 1 % mod;
LL dqans = ksm(a, y >> 1, mod);
if (y & 1)
return ((dqans * dqans) % mod * a) % mod;
else
return dqans * dqans % mod;
}

小白逛公园

水 线段树维护区间最大子串, 不允许不选

注意题目里说$left > right$的时候不是输出0而是把他们swap一下…

不算题意杀的话也是1A吧…感觉线段树合并的话这样写很资瓷?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (500000 + 5)
#define INF (0x7ffffff)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
struct node
{
int le, ri, sum, lz, rz, maxz;
}b[MAXN << 3];
int a[MAXN];
node push_up(node ls, node rs)
{
node re;
re.le = ls.le, re.ri = rs.ri;
re.sum = ls.sum + rs.sum;
re.lz = max(ls.lz, ls.sum + rs.lz);
re.rz = max(rs.rz, rs.sum + ls.rz);
re.maxz = max(max(ls.maxz, rs.maxz), max(max(re.lz, re.rz), ls.rz + rs.lz));
return re;
}
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
if (le == ri)
{
b[dq].sum = a[le];
b[dq].maxz = b[dq].lz = b[dq].rz = max(-INF, a[le]);
return ;
}
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
b[dq] = push_up(b[LS(dq)], b[RS(dq)]);
}
void xg(int dq, int wz, int zh)
{
if (b[dq].le == b[dq].ri)
{
b[dq].sum = zh;
b[dq].maxz = b[dq].lz = b[dq].rz = max(-INF, zh);
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz > mi)
xg(RS(dq), wz, zh);
else
xg(LS(dq), wz, zh);
b[dq] = push_up(b[LS(dq)], b[RS(dq)]);
}
node cx(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
return b[dq];
int mi = (b[dq].le + b[dq].ri) >> 1;
if (ri <= mi)
return cx(LS(dq), le, ri);
else if (le > mi)
return cx(RS(dq), le, ri);
else
return push_up(cx(LS(dq), le, mi), cx(RS(dq), mi + 1, ri));
}
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
js(1, 1, n);
for (int i = 1; i <= q; i++)
{
int sre, srx, sry;
scanf("%d%d%d", &sre, &srx, &sry);
if (sre & 1)
{
if (srx > sry)
swap(srx, sry);
printf("%d\n", cx(1, srx, sry).maxz);
}
else
xg(1, srx, sry);
}
return 0;
}

CoVH之柯南开锁

二分图在棋盘上的经典应用, 将横坐标看做节点都连到$X$集合, 纵坐标也看成节点都连到$Y$集合, 对于每一个点, 连接他相应的横纵坐标对应的点即可

还行吧…15min就1A了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <string>
#define MAXN (100000 + 5)
#define INF (0x7ffffff)
#define rev(a) ((((a) - 1) ^ 1) + 1)
#define bh(a) ((a) + 1000)
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
int from, to, next, cap, flow;
edg() {}
edg(int fr, int dqt, int ne, int ca, int fl): from(fr), to(dqt), next(ne), cap(ca), flow(fl) {}
}b[MAXN << 1];
int g[MAXN], cntb, dis[MAXN];
void adn(int from, int to, int cap)
{
b[++cntb] = edg(from, to, g[from], cap, 0);
g[from] = cntb;
}
int bfs()
{
queue<int> q;
q.push(s);
memset(dis, 0, sizeof(dis));
dis[s] = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
if (!dis[b[i].to] && b[i].cap > b[i].flow)
dis[b[i].to] = dis[dq] + 1, q.push(b[i].to);
}
return dis[t];
}
int dinic(int dq, int maxf)
{
if (dq == t || !maxf)
return maxf;
int re = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
{
int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
maxf -= zl;
re += zl;
b[i].flow += zl;
b[rev(i)].flow -= zl;
}
}
return re;
}
int main()
{
int n, m;
string ss;
cin >> n >> m;
for (int i = 1; i <= m; i++)
adn(bh(i), t, 1), adn(t, bh(i), 0);
for (int i = 1; i <= n; i++)
{
adn(s, i, 1);
adn(i, s, 0);
cin >> ss;
for (int j = 0; j < m; j++)
{
if (ss[j] == '1')
{
adn(i, bh(j + 1), 1);
adn(bh(j + 1), i, 0);
}
}
}
int ans = 0;
while (bfs())
ans += dinic(s, INF);
cout << ans;
return 0;
}

总算把入门写完了…srO AH老师

By Cansult