开始套题训练，第一套ASC题目，记住不放过每一题，多独立思考。
Problem A ZOJ 2313 Chinese Girls' Amusement 循环节
题意：给定n，为圆环长度，求k <= n/2,从1出发，每次顺时针方向走k步，即1->k+1->2*k+1,直到遇到一个已经走过的点结束，要求最终把所有点访问一遍，最后回到1，使得k尽量大。
代码：
Problem B ZOJ 2314 Reactor Cooling 无源汇上下界网络流
题意：经典题，有上下界无源无汇的可行流，对于每条边u->v，上界流量C(u,v),下界流量B(u, v)，可以这样构图，建立附加源点S，T对于每条边u->v，在流量图中连一条容量为C(u, v)-B(u, v)的边，同时S->v连容量B(u, v) 的边，u->T连B(u, v) 的边，跑一遍网络流，当从S出发的边满流时，有可行流，原图中每条边流量为相应B(u, v)+最大流图中流量g(u, v).
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair #define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef map<int, int> MPS;
typedef pair<int, int> PII;
const int maxn = ;
struct Node {
int c, l, id;
Node() {}
Node(int c, int l, int id):c(c), l(l), id(id) {}
};
vector<Node> cap; struct Edge {
int u, v, c;
Edge(int u, int v, int c):u(u), v(v), c(c) {}
};
struct Max_flow {
int n, m;
int src, sink;
vector<Edge> edges;
vector<int> G[maxn];
int Now[maxn], Dfn[maxn], cur[maxn];
void init(int n) {
this->n = n;
for(int i = ; i < n; i++) G[i].clear();
edges.clear();
}
void add(int u, int v, int c) {
edges.pb(Edge(u, v, c));
edges.pb(Edge(v, u, ));
m = edges.size();
G[u].pb(m-);
G[v].pb(m-);
}
int ISAP(int s, int flow) {
if(s == sink)
return flow;
int i, tab = n, vary, now = ;
int p = cur[s];
do {
Edge &e = edges[G[s][cur[s]]];
if(e.c > ) {
if(Dfn[s] == Dfn[e.v]+)
vary = ISAP(e.v, min(flow-now, e.c)),
now += vary, e.c -= vary, edges[G[s][cur[s]]^].c += vary;
if(Dfn[src] == n)
return now;
if(e.c > ) tab = min(tab, Dfn[e.v]);
if(flow == now)
break;
}
cur[s]++;
if(cur[s] == (int)G[s].size()) cur[s] = ;
} while(p != cur[s]);
if(now == ) {
if(--Now[Dfn[s]] == )
Dfn[src] = n;
Now[Dfn[s] = tab+]++;
}
return now;
}
int max_flow(int src, int sink) {
this->src = src;
this->sink = sink;
int flow = ;
memset(Dfn, , sizeof Dfn);
memset(Now, , sizeof Dfn);
memset(cur, , sizeof cur);
Now[] = n;
for(; Dfn[src] < n;)
flow += ISAP(src, inf);
return flow;
}
} mc;
vector<int> mx; int main() { int T;
for(int t = scanf("%d", &T); t <= T; t++) {
int n, m;
cap.clear();
mx.clear(); scanf("%d%d", &n, &m);
mc.init(n+);
int src = n, sink = n+; for(int i = ; i <= m; i++) {
int u, v, c, l;
scanf("%d%d%d%d", &u, &v, &l, &c);
u--, v--;
mc.add(u, v, c-l);
int tmp = mc.edges.size()-;
cap.pb(Node(c, l, tmp));
mc.add(src, v, l);
tmp = mc.edges.size()-;
mx.pb(tmp);
mc.add(u, sink, l);
}
int flow = mc.max_flow(src, sink);
//// cout << flow << endl;
int ok = 1;
for(int i = ; i < (int)mx.size(); i++) {
int id = mx[i];
if(mc.edges[id].c) {
ok = ;
break;
}
} if(t != ) puts("");
if(ok) {
puts("YES");
for(int i = ; i < (int)cap.size(); i++) {
Node x = cap[i];
int id = x.id;
printf("%d\n", x.c-mc.edges[id].c);
}
} else puts("NO");
}
return ;
}
关于上下界网络流补充资料：http://blog.sina.com.cn/s/blog_76f6777d0101bara.html
Problem C ZOJ 2315 New Year Bonus Grant 树形dp或贪心
题意：以1为根的树中，每个结点可以从父节点获得一个奖励，或者自己给其中一个子节点的奖励，或者既不获得也不给出奖励。求所有结点获得的最大奖励数目
分析：我是用树形dp做的，dp[u][i]，i为1表示从父亲结点获得奖励时该子树最大奖励和，dp[u][0]为不从父节点获得奖励时该子树的最大奖励和。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair #define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef map<int, int> MPS;
typedef pair<int, int> PII;
const int maxn = (int)5e5 + ;
vector<int> g[maxn];
int dp[maxn][], pa[maxn];
void dfs(int u, int fa) {
int sum = ;
dp[u][] = dp[u][] = -;
pa[u] = -;
for(int i = ; i < sz(g[u]); i++) {
int v = g[u][i];
if(v == fa) continue;
dfs(v, u);
sum += dp[v][];
}
dp[u][] = + sum;
dp[u][] = sum;
for(int i = ; i < sz(g[u]); i++) {
int v = g[u][i];
if(v == fa) continue;
if(sum-dp[v][]+dp[v][] > dp[u][])
dp[u][] = sum-dp[v][]+dp[v][], pa[u] = v;
}
}
vector<int> ans;
void printAns(int u, int st, int fa) {
if(st) ans.pb(u);
for(int i = ; i < sz(g[u]); i++) {
int v = g[u][i];
if(v == fa) continue;
printAns(v, v == pa[u] && !st, u);
}
}
int main() { int T;
for(int t = scanf("%d", &T); t <= T; t++) {
if(t != ) puts("");
int n;
ans.clear();
scanf("%d", &n);
for(int i = ; i <= n; i++) g[i].clear();
for(int i = ; i < n; i++) {
int u;
scanf("%d", &u);
g[u].pb(i+);
}
dfs(, );
printf("%d\n", *dp[][]);
printAns(, , );
sort(ans.begin(), ans.end());
for(int i = ; i < (int)ans.size(); i++) {
printf("%d%c", ans[i], i == (int)ans.size()- ? '\n' : ' ');
}
}
return ;
}
Problem D ZOJ 2316 Matrix Multiplication 顶点度数
题意：给定一个图，n个顶点，m条边，最终就是要你求每个点度数平方之和。
分析：注意防止溢出。
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair #define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef map<int, int> MPS;
MPS mps; const int maxn = + ;
int num[maxn];
int cnt; int idx(int x){
if(mps.count(x) == false)
mps[x] = ++cnt;
return mps[x];
}
int main(){ int T;
for(int t = scanf("%d", &T); t <= T; t++){
memset(num, , sizeof num);
int n, m;
mps.clear();
cnt = ;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++){
int u, v;
scanf("%d%d", &u, &v);
u = idx(u);
v = idx(v);
num[u]++, num[v]++;
}
LL ans = ;
for(int i = ; i <= n;i++){
ans += (LL)num[i]*num[i];
}
if(t != ) puts("");
printf("%lld\n", ans);
}
return ;
}
Problem E ZOJ 2317 Nice Patterns Strike Back 矩阵快速幂，组合数
题意：一个n*m的方格，每个格子有两种颜色，现在给整个方格涂色，要求一个2*2的正方形内颜色不能相同，问有多少种颜色，m<=5, n <= 10^100，最终结果模p，p <= 10000。
分析：由于能否构成同样颜色正方形取决于当前列连续2格以及前一列的对应两列是否颜色一样，所以对每列的状态，st看能从哪些状态st'转移过来。这样可以建立一个转移图
边u->v表示前一列状态为u下列可为v。dp[i+1][u] = sum{dp[i][v]}，可以得到一个矩阵，g[v][u]表示v转移到u，那么答案就是g^n然后取结果矩阵sum{g[i][0]}之和。
代码：
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define esp 1e-8
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef map<int, int> MPS;
typedef pair<int, int> PII; const int maxn = ;
const int maxm = ;
const int B = ;
int m, p; struct BigInt {
int dig[maxn], len;
BigInt(int num = ):len(!!num) {
memset(dig, , sizeof dig);
dig[] = num;
}
int operator [](int x)const {
return dig[x];
}
int& operator [](int x) {
return dig[x];
}
BigInt normalize() {
while(len && dig[len-] == ) len--;
return *this;
}
void output() {
if(len == ) {
puts("");
return;
}
printf("%d", dig[len-]);
for(int i = len-; i >= ; i--)
printf("%04d", dig[i]);
puts("");
}
};
BigInt operator / (BigInt a, int b) {
BigInt c;
c.len = a.len;
for(int i = a.len-, delta = ; i >= ; i--) {
delta = delta*B+a[i];
c[i] = delta/b;
delta %= b;
}
return c.normalize();
}
bool operator == (const BigInt &a, const BigInt &b) {
if(a.len != b.len) return false;
for(int i = a.len-; i >= ; i--) if(a[i] != b[i]) return false;
return true;
}
struct Matrix {
int a[maxm][maxm];
Matrix() {
memset(a, , sizeof a);
}
};
Matrix operator * (const Matrix &a, const Matrix &b) {
Matrix c;
for(int i = ; i < (<<m)+; i++) for(int j = ; j < (<<m)+; j++) {
for(int k = ; k < (<<m)+; k++)
c.a[i][j] = (c.a[i][j] + (LL)a.a[i][k]*b.a[k][j]%p)%p;
}
return c;
}
char s[];
int b[] = {, , , }; bool check(int x, int y) {
for(int i = ; i < m-; i++) {
if((((x>>i)&) && ((x>>(i+))&)
&& ((y>>i)&) && ((y>>(i+))&)) || (!((x>>i)&) && !((x>>(i+))&)
&& !((y>>i)&) && !((y>>(i+))&)))
return false;
}
return true;
}
int main() { int T;
for(int t = scanf("%d", &T); t <= T; t++) {
if(t != ) puts("");
scanf("%s%d%d", s, &m, &p);
int len = strlen(s);
BigInt c;
for(int i = len-; i >= ; i--) {
c[(len--i)/] += b[(len--i)%]*(s[i]-'');
c.len = max(c.len, (len--i)/+);
}
Matrix res, g;
for(int i = ; i < maxm; i++) for(int j = ; j < maxm; j++) res.a[i][j] = i == j;
for(int i = ; i < (<<m); i++) {
g.a[i+][] = ;
for(int j = ; j < (<<m); j++) if(check(i, j)) {
g.a[j+][i+] = ;
}
}
while(c.len) {
if(c[]&) res = res*g;
g = g*g;
c = c/;
}
int ans = ;
for(int i = ; i <= (<<m); i++)
ans = (ans + res.a[i][])%p ;
printf("%d\n", ans);
}
return ;
}
一个升级版的题目，不过要用到中国剩余定理：
hdu 4878 ZCC loves words AC自动机+中国剩余定理+快速幂
Problem F ZOJ 2318 Get Out! 有向角度判别法，spfa判负环
题意：给定一些圆，然后自己也是一个圆能否从中突出重围。
分析：将自己的半径加到其他圆上面，并平移坐标系以自己所在坐标为原点，将相交的圆心连一条边，然后问题变成了，看是否有一个多边形包围原点。利用有向视角判别法，每条边两个顶点与原点构成的角度a作为权值，对应原来的边建图，两条有向边，权值对应为a和-a。这样就看原图是否有负环了。利用spfa判别就行。位于多边形外面时显然角度和位0。内部则为360或-360度
注意：本题分析显然不会位于多边形顶点或边界上面，否则可能会出错？spfa判别法注意精度。
代码：
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <queue>
#define pb push_back
#define mp make_pair
#define esp 1e-8
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef map<int, int> MPS;
typedef pair<int, int> PII; const int maxn = ;
double x[maxn], y[maxn], r[maxn], len[maxn]; struct Edge {
int u, v;
double w;
Edge() {}
Edge(int u, int v, double w):u(u), v(v), w(w) {}
};
vector<Edge> edges;
vector<int> g[maxn];
int n, m; void init() {
edges.clear();
for(int i = ; i < maxn; i++) g[i].clear();
}
void add(int u, int v, double w) {
edges.pb(Edge(u, v, w));
m = edges.size();
g[u].pb(m-);
}
inline bool check(double x1, double y1, double x2, double y2) {
return (x1*y2-y1*x2) >= ;
}
int inq[maxn];
double dist[maxn];
int cnt[maxn]; bool spfa() {
queue<int> q;
memset(inq, , sizeof inq);
for(int i = ; i <= n; i++) {
inq[] = ;
cnt[i] = ;
dist[i] = ;
q.push(i);
} while(q.size()) {
int u = q.front();
q.pop();
inq[u] = ;
for(int i = ; i < sz(g[u]); i++) {
Edge e = edges[g[u][i]];
int v = e.v;
double c = e.w;
if(dist[v] > dist[u] + c + esp) {
if(dist[v] = dist[u] + c, !inq[v]) {
q.push(v);
inq[v] = ;
if(++cnt[v] > n + ) {
return true;
}
}
}
}
}
return false;
}
int main() { int T;
for(int t = scanf("%d", &T); t <= T; t++) {
if(t != ) puts("");
init();
for(int i = scanf("%d", &n); i <= n+; i++) {
scanf("%lf%lf%lf", x+i, y+i, r+i);
}
for(int i = ; i <= n; i++) {
x[i] -= x[n+];
y[i] -= y[n+];
len[i] = sqrt(pf(x[i])+pf(y[i]));
r[i] += r[n+];
}
for(int i = ; i <= n; i++)
for(int j = i+; j <= n; j++) {
if(sqrt(pf(x[i]-x[j]) + pf(y[i]-y[j])) >= r[i]+r[j])
continue;
double ang = acos((x[i]*x[j]+y[i]*y[j])/len[i]/len[j]);
bool ok = check(x[i], y[i], x[j], y[j]);
add(i, j, ok ? ang : -ang);
add(j, i, ok ? -ang : ang);
}
if(spfa())
puts("NO");
else puts("YES");
}
return ;
}
Problem G ZOJ 2319 Beautiful People LIS
题意：有n个元素，每个元素是一个对数ai,bi，然后从中选出一些元素，能够排成一列ai < ai+1, 且bi < bi+1,问最长选出多少个元素。
分析：看上去像是LIS，其实也是利用这个，由于ai肯定是单调递增的，所以先按ai小到大排序，bi从大到小排序，然后只要按照bi选出LIS就行了。利用O(nlogn)的经典做法可做。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair #define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef map<int, int> MPS;
typedef pair<int, int> PII; const int maxn = (int)1e5 + ;
int f[maxn], dp[maxn];
MPS mps; struct Node {
int s, b, id;
Node() {}
Node(int s, int b, int id):s(s), b(b), id(id) {}
bool operator < (const Node &rhs)const {
if(s != rhs.s) return s < rhs.s;
return b > rhs.b;
}
} a[maxn];
int g[maxn];
int cnt;
int idx(int x) {
if(mps.count(x) == false)
mps[x] = ++cnt;
return mps[x];
} int main() { int T;
for(int t = scanf("%d", &T); t <= T; t++) {
int n;
cnt = ;
if(t != ) puts("");
scanf("%d", &n);
mps.clear();
for(int i = ; i <= n; i++) {
scanf("%d%d", &a[i].s, &a[i].b);
//// a[i].s = idx(a[i].s);
//// a[i].b = idx(a[i].b);
a[i].id = i;
}
memset(dp, , sizeof dp);
sort(a+, a+n+);
memset(f, 0x7f, sizeof f);
int ans = , u;
for(int i = ; i <= n; i++) {
int k = lower_bound(f+, f+n+, a[i].b)-f-;
if(ans < k+)
ans = k+, u = i;
f[k+] = a[i].b;
g[k+] = i;
dp[i] = g[k];
}
cout << ans << endl;
int ok = ;
while(u) {
if(ok) cout << ' ';
else ok ^= ;
cout << a[u].id;
u = dp[u];
}
puts("");
}
return ;
}
Problem H ZOJ 2320 Cracking' RSA 高斯消元
题意：给定m个数，其素因子来自前t个素数，m <= 100，t <= 100。求m个数构成的集合，从中选出一些数构成子集，所有元素之积为完全平方数。有多少种方案。
分析：考虑每个数有选和不选两种状态，用未知量xi表示，由于最终选出来的数的积为完全平方数，所以其乘积中，对于前t个素数的数目必须为偶数个，即模2为0。
所以容易建立t个方程，对每个数分解质因数，质因数个数模2为0，这是一个线性方程组，方程一定有解，所以设*元个数n，答案2^n-1，这里要用到大数。
代码：
#include <iostream>
#include <cstdio>
#include <map> #include <cstring>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define esp 1e-8
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef map<int, int> MPS;
typedef pair<int, int> PII; const int maxn = ;
const int B = ; int num[maxn][maxn], prime[maxn], vis[];
int a[maxn][maxn];
void seivePrime() {
int tot = ;
for(int i = ; i < ; i++) {
if(!vis[i]) prime[++tot] = i; for(int j = ; j <= tot; j++){
if(prime[j]*i >= ) break;
vis[i*prime[j]] = ;
if(i%prime[j] == ) break;
}
if(tot >= ) break;
}
}
int n, m;
void getFact(int b, LL x) {
for(int i = ; i <= n; i++) {
if(x%prime[i] == ) {
while(x%prime[i] == ) {
num[b][i-]++;
x /= prime[i];
}
if(x == )
break;
}
}
}
int Gauss(int equ, int var) {
int k, r, col;
for(k = col = ; k < equ && col < var; k++, col++) {
r = k;
for(int i = k+; i < equ; i++) if(a[i][col]) {
r = i;
break;
}
if(r != k) for(int i = col; i <= var; i++)
swap(a[r][i], a[k][i]);
if(a[k][col] == ) {
k--;
continue;
}
for(int i = k+; i < equ; i++) if(a[i][col])
for(int j = col; j <= var; j++)
a[i][j] ^= a[k][j];
}
return var-k;
}
struct BigInt {
int dig[maxn], len;
BigInt(int num = ):len(!!num) {
memset(dig, , sizeof dig);
dig[] = num;
}
int operator [](int x)const {
return dig[x];
}
int &operator [](int x) {
return dig[x];
}
BigInt normalize() {
while(len > && dig[len-] == ) len--;
return *this;
}
void output() {
printf("%d", dig[len-]);
for(int i = len-; i >= ; i--)
printf("%04d", dig[i]);
puts("");
}
};
BigInt operator - (BigInt a, int b) {
BigInt c;
c.len = a.len;
for(int i = , delta = -b; i < a.len; i++) {
c[i] = delta+a[i];
delta = ;
if(c[i] < ) {
delta = -;
c[i] = c[i]+B;
}
}
return c.normalize();
}
BigInt operator *(BigInt a, BigInt b) {
BigInt c;
c.len = a.len+b.len+;
for(int i = ; i < a.len; i++)
for(int j = , delta = ; j <= b.len; j++) {
delta += (c[i+j]+a[i]*b[j]);
c[i+j] = delta%B;
delta /= B;
}
return c.normalize();
}
void print(int x){
int i , len = , ans[];
memset(ans,,sizeof(ans));
ans[] = ;
while (x--){
for (i=;i<=len;++i) ans[i]*=;
for (i=;i<=len;++i)
ans[i+] += ans[i]/ , ans[i] %= ;
if (ans[len+]) ++len;
}
--ans[];
for (i=len;i>=;--i) printf("%d",ans[i]);
puts("");
}
int main() { int T;
seivePrime();
for(int t = scanf("%d", &T); t <= T; t++) {
if(t != ) puts("");
memset(num, , sizeof num);
memset(a, , sizeof a);
scanf("%d%d", &n, &m);
for(int i = ; i < m; i++) {
int x;
scanf("%d", &x);
for(int ii = ; ii <= n; ii++) {
if(x%prime[ii] == ) {
while(x%prime[ii] == ) {
a[ii-][i] ^= ;
x /= prime[ii];
}
}
}
}
int vary = Gauss(n, m);
if(vary == ) puts("");
else
print(vary);
}
return ;
}