OI
9 minutes read (About 1375 words)

20161025测试总结

T1

此题推了一个小时的网络流，然后拆点写挂…

100分

最大流，将所有点 u 都拆分成 u1 和 u2，s 向 u1 连容量为 F 的边，u2 向 t 连容量为 F 的边。对于原图的边 (u, v)，建立边 (u1, v2)，容量为 w(u, v)。
这样答案为 $\sum F_{i} - MaxFlow$

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
using namespace std;
#define clear(a, b) memset (a, b, sizeof(a))
#define copy(a, b) memcpy (a, b, sizeof(a))
const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
inline char read() {
    if(ioh == iot) {
        iot = (ioh = buf) + fread(buf, 1, iol, stdin);
        if(ioh == iot) return -1;
    }
    return *ioh++;
}
template<class T>
inline bool read(T &x) {
    iosig = false;
    for (ioc = read(); !isdigit(ioc); ioc = read()) {
        if (ioc == -1) return false;
        if (ioc == '-') iosig = true;
    }
    x = 0;
    while(ioc == '0') ioc = read();
    for(; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
    ioh--;
    if(iosig) x = -x;
    return true;
}
const int MAXN = 101000;
const int MAXE = 500100;  
const int INF = 0x3f3f3f3f;
struct Edge {
    int v;/*弧尾*/
    int c;/*容量*/
    int n;/*指向下一条从同一个弧头出发的弧*/
} edge[MAXE];/*边组*/
int adj[MAXN], cnt;/*前向星的表头*/
int dis[MAXN], cur[MAXN], pre[MAXN], num[MAXN];
int s, t, nv;/*s：源点，t：汇点，nv：编号修改的上限*/
int n, m;
inline void addEdge(int u, int v, int c) {/*添加边
    /*正向边*/
    edge[cnt].v = v;
    edge[cnt].c = c;/*正向弧的容量为c*/
    edge[cnt].n = adj[u];
    adj[u] = cnt++;
 
    /*反向边*/
    edge[cnt].v = u;
    edge[cnt].c = 0;/*反向弧的容量为0*/
    edge[cnt].n = adj[v];
    adj[v] = cnt++;
}
inline void bfs(int t) {/*反向BFS标号 */
    clear (num, 0), clear (dis, -1);/*没标过号则为-1 */
    dis[t] = 0;/*汇点默认为标过号 */
    num[0] = 1;
    queue<int> q;
    q.push(t);
    while(!q.empty()) {
        register int u = q.front();
        q.pop();
        for(register int i = adj[u], v; ~i; i=edge[i].n) {
            v=edge[i].v;
            if(~dis[v]) continue;/*已经标过号*/
            dis[v] = dis[u] + 1;/*标号*/
            q.push(v);
            ++num[dis[v]];
        }
    }
}
inline int isap(int s, int t, int nv) { 
    copy(cur, adj);/*复制，当前弧优化 */
    bfs(t);/*只用标号一次就够了，重标号在ISAP主函数中进行就行了 */
    int flow = 0, u = pre[s] = s, i; 
    while (dis[t] < nv) {/*最长也就是一条链，其中最大的标号只会是nv - 1，如果大于等于nv了说明中间已经断层了。 */
        if (u == t) {/*如果已经找到了一条增广路，则沿着增广路修改流量 */
            int f = INF, neck;
            for (i = s; i != t; i = edge[cur[i]].v) {
                if (f > edge[cur[i]].c) {
                    f = edge[cur[i]].c;/*不断更新需要减少的流量*/
                    neck = i;/*记录回退点，目的是为了不用再回到起点重新找*/
                }
            }
            for (i = s; i ^ t; i = edge[cur[i]].v) {/*修改流量*/
                edge[cur[i]].c -= f;
                edge[cur[i] ^ 1].c += f;
            }
            flow += f;/*更新*/
            u = neck;/*回退*/
        }
        for (i = cur[u]; ~i; i = edge[i].n) if (dis[edge[i].v] + 1 == dis[u] && edge[i].c) break;
        if (~i) {/*如果存在可行增广路，更新*/
            cur[u] = i;/*修改当前弧*/
            pre[edge[i].v] = u;
            u = edge[i].v;
        }else {/*否则回退，重新找增广路*/
            if (0 == (--num[dis[u]])) break;/*GAP间隙优化，如果出现断层，可以知道一定不会再有增广路了*/
            int mind = nv;
            for (i = adj[u]; ~i; i = edge[i].n) {
                if (edge[i].c && mind > dis[edge[i].v]) {/*寻找可以增广的最小标号*/
                    cur[u] = i;/*修改当前弧*/
                    mind = dis[edge[i].v];
                }
            }
            dis[u] = mind + 1;
            num[dis[u]]++;
            u = pre[u];/*回退*/
        }
    }
    return flow;
}
#define init() clear(adj, -1), cnt = 0
int tot, ans;
int main(){
    init();
    read(n), read(m);
    s = tot = ans = 0, t = n << 1 | 1;
    for (register int i = 1, w; i <= n; i++)
        read(w), ans += w, addEdge(s, i, w), addEdge(i + n, t, w);
    for (register int i = 0, u, v, w; i < m; i++)
        read(u), read(v), read(w), addEdge(u, v + n, w);
    nv = t - s + 1;
    s = s, t = t;
    cout << ans - isap(s, t, nv);
    return 0;
}

T2

数位dp，没想出7的倍数的转移…
可以维护一下mod值，每次*10再%7就233了
注意不要作死多记一个pre，

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
#include <bits/stdc++.h>
using namespace std;
const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
inline char read() {
    if(ioh == iot) {
        iot = (ioh = buf) + fread(buf, 1, iol, stdin);
        if(ioh == iot) return -1;
    }
    return *ioh++;
}
template<class T>
inline bool read(T &x) {
    iosig = false;
    for (ioc = read(); !isdigit(ioc); ioc = read()) {
        if (ioc == -1) return false;
        if (ioc == '-') iosig = true;
    }
    x = 0;
    while(ioc == '0') ioc = read();
    for(; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
    ioh--;
    if(iosig) x = -x;
    return true;
}
int len = 0;
long long dp[20][2][7], digits[20];
long long dfs(int pos, int status, int limit, int mod) {
    if(pos < 1) return ((!mod) || status ? 1 : 0);
    if(!limit && dp[pos][status][mod] != -1)
        return dp[pos][status][mod];
    register int end = limit ? digits[pos] : 9;
    register long long ret = 0;
    for(register int i = 0; i <= end; i++)
        ret += dfs(pos - 1, status || i == 7, limit && (i == end), ((mod << 1) + (mod << 3) + i) % 7);
    if(!limit)
        dp[pos][status][mod] = ret;
    return ret;
}
inline long long solve(long long x) {
    len = 0;
    while(x) {
        digits[++len] = x % 10;
        x /= 10;
    }
    memset(dp, -1, sizeof(dp));
    return dfs(len, 0, 1, 0);
}
int n;
long long l, r;
int main() {
    read(n);
    while(n--) {
        read(l), read(r);
        cout << solve(r) - solve(l - 1) << "\n";
    }
    return 0;
}

T3

据说此题最简单，T1、T2耗尽大部分时间的我就233了…
注意到此题数据中的a的范围<=100000，故此题可以先按a、x、y交换建图，暴力枚举w，然后简单的一维dp一下就好了

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
#include <bits/stdc++.h>
using namespace std;
const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
inline char read() {
    if(ioh == iot) {
        iot = (ioh = buf) + fread(buf, 1, iol, stdin);
        if(ioh == iot) return -1;
    }
    return *ioh++;
}
template<class T>
inline bool read(T &x) {
    iosig = false;
    for (ioc = read(); !isdigit(ioc); ioc = read()) {
        if (ioc == -1) return false;
        if (ioc == '-') iosig = true;
    }
    x = 0;
    while(ioc == '0') ioc = read();
    for(; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
    ioh--;
    if(iosig) x = -x;
    return true;
}
const int MAX = 3e5 + 20;
vector<pair<int, int> > edge[MAX];
int n, m, f[MAX], g[MAX];
inline void addEdge(int u, int v, int w) {
    edge[u].push_back(make_pair(v, w));
}
int main() {
    read(n), read(m);
    for (register int i = 0, u, v, w; i < m; i++)
        read(u), read(v), read(w), addEdge(w, u, v);
    vector<pair<int, int> > *e;
    for (register int w = 1; w <= 100000; w++) {
        e = &edge[w];
        if(e->empty()) continue;
        for (vector<pair<int, int> >::iterator it = e->begin(); it != e->end(); it++)
            g[it->first] = f[it->first], g[it->second] = f[it->second];
        for (vector<pair<int, int> >::iterator it = e->begin(); it != e->end(); it++)
            f[it->second] = std::max(f[it->second], g[it->first] + 1);
    }
    cout << *max_element(f + 1, f + n + 1);
    return 0;
}
20161026测试总结
20161020测试总结

Comments

Follow

Tag Cloud

Algorithm CG DP Data Structure Frontend Geometry Graph Theory Hash Hexo Language Math Note Ray Tracing Rendering STL String Test

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×