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

我是不是成弃坑大师了…

捕风捉影

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

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

#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吧…感觉线段树合并的话这样写很资瓷?

#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了…

#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