2017 训练赛 1 by hzwer
「poj1054」The Troublesome Frog（恼人的青蛙）
「poj1037」decorative fence
「hdu2462」The Luckiest number
「bzoj3172」[Tjoi2013]单词
「poj1054」The Troublesome Frog（恼人的青蛙）
首先O(n^3)的算法是显然的，即枚举两个点，check一下这条路径上所有点，由于这道题时限放的比较宽，实际上图可以直接用二维的bool数组存下来
网络上的题解大多都说是暴力剪枝水过，实际上可以证明某个简单的优化可以把复杂度降到O(n^2)
我们注意到，如果纯暴力的话，一条路径会被重复check很多次，我们可以想到，强制使得选定的两个点是开头两个，即检查前一个点是否在图外，那么这样一条路径仅会被check一次
下证复杂度
对任意三个脚印A，B，C，若AB = BC且在同一条直线上，我们把AB边，BC边抽象成新图中的点，并把新图中的这两个点连成边，这样构建一张新图
新图的点数是O(n^2)的，由于每个点度数至多是2，所以边数也是O(n^2)的，而且是一张只有链的图，那么我们可以暴力在新图上找出最长链。其实，上面给出的暴力优化，就是在新图上找一个链头，并沿着这条链得出它的长度，新图的每条边仅会被check一次，故暴力优化的复杂度是O(n^2)
由于时限卡的比较紧，需要一些常数优化
|
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 |
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define inf 1000000000 using namespace std; int r, c, n; struct data{ int x, y; }p[5005]; bool a[5005][5005]; int gcd(int a, int b) { return b == 0? a : gcd(b, a % b); } bool operator<(data a, data b) { if(a.x == b.x)return a.y < b.y; return a.x < b.x; } inline bool check(int x, int y) { if(x < 1 || y < 1 || x > r || y > c)return 0; return 1; } int main() { cin >> r >> c >> n; for(int i = 1; i <= n; i++) { scanf("%d%d", &p[i].x, &p[i].y); a[p[i].x][p[i].y] = 1; } int ans = 0; sort(p + 1, p + n + 1); for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) { int x = p[i].x, y = p[i].y; int dx = p[j].x - x, dy = p[j].y - y; if(x + dx * ans > r)break; if(check(x - dx, y - dy))continue; if(check(x + dx * ans, y + dy * ans)) { int cnt = 0, flag = 1; while(1) { x += dx; y += dy; if(!check(x, y))break; else { if(a[x][y])cnt++; else { flag = 0; break; } } } if(flag)ans = max(ans, cnt); } } if(ans <= 2)puts("0"); else cout << ans + 1 << endl; return 0; } |
用g(i,j)表示长度为i，开头为j，开头为下降(a0 > a1)的序列
从小到大dp每个数字，考虑把第i个数字放在长度为i-1的上升序列之前，变成下降序列
或放在长度为i-1的下降序列的第2位，变成上升序列
预处理完之后，类似求第K大的全排列的方法，按照排名一位一位确定每一个数字
|
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 |
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int T, n; ll C; ll f[25][25], g[25][25]; int ans[25]; bool vis[25]; void dp() { f[1][1] = g[1][1] = 1; for(int i = 2; i <= 20; i++) for(int j = 1; j <= i; j++) { for(int k = 1; k <= j - 1; k++) g[i][j] += f[i - 1][k]; for(int k = j; k <= i - 1; k++) f[i][j] += g[i - 1][k]; } } int main() { dp(); cin >> T; while(T--) { memset(vis, 0, sizeof(vis)); memset(ans, 0, sizeof(ans)); cin >> n >> C; for(int i = 1; i <= n; i++) { int cnt = 0; for(int j = 1; j <= n; j ++) if(!vis[j]) { ll tmp = C; cnt++; if(i == 1) C -= f[n][cnt] + g[n][cnt]; else if(j > ans[i - 1] && (i == 2 || ans[i - 2] > ans[i - 1]))C -= g[n - i + 1][cnt]; else if(j < ans[i - 1] && (i == 2 || ans[i - 2] < ans[i - 1]))C -= f[n - i + 1][cnt]; if(C <= 0) { ans[i] = j; vis[j] = 1; C = tmp; break; } } } for(int i = 1; i <= n; i++) cout << ans[i] << ' '; cout << endl; } return 0; } |
\(f_n=2^n – \sum{f_i}(i|n)-2\)
|
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 |
#include <set> #include <map> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long #define mod 2008 using namespace std; int n; map<int, int> mp; int pow(int x) { ll ans = 1, a = 2; for(int i = x; i; i >>= 1, a = a * a % mod) if(i & 1)ans = ans * a % mod; return ans; } int f(int n) { if(n == 1)return 2; if(mp[n])return mp[n] - 1; ll ans = (pow(n) - 2 + mod) % mod; for(int i = 2; i <= sqrt(n); i++) if(n % i == 0) { if(i * i != n)ans -= f(i) + f(n / i); else ans -= f(i); ans %= mod; if(ans < 0)ans += mod; } mp[n] = ans + 1; return ans; } int main() { while(cin >> n) { cout << f(n) << endl; } return 0; } |
二分距离mid，将距离小于mid的奶牛和挤奶器连边，用最大流判断可行性
|
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 |
#include <iostream> #include <cstring> #define T (n+m+1) #define inf 1000000000 using namespace std; int n, m, mx, cnt = 1, ans; int a[405][405]; int last[405],h[405],q[405]; struct data{ int to, next, v; }e[1000005]; void insert(int u, int v, int w) { e[++cnt] = (data){v, last[u], w};last[u]=cnt; e[++cnt] = (data){u, last[v], 0};last[v]=cnt; } int bfs() { int head = 0, tail = 1; for(int i = 0; i <= T; i++)h[i] = -1; h[0] = 0; q[0] = 0; while(head != tail) { int now = q[head];head++; for(int i = last[now];i;i =e[i].next) if(h[e[i].to] == -1 && e[i].v) { h[e[i].to] = h[now] + 1; q[tail++] = e[i].to; } } return h[T] != -1; } int dfs(int x, int f) { if(x == T) return f; int w, used = 0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to] == h[x] + 1) { w = dfs(e[i].to,min(f-used,e[i].v)); used += w; e[i].v -= w;e[i^1].v += w; if(used == f)return f; } if(!used)h[x] = -1; return used; } bool check(int x) { memset(last,0,sizeof(last)); cnt = 1; for(int i = 1;i<=n;i++) insert(0,i,mx); for(int i = 1;i<=m;i++) insert(i + n,T,1); for(int i = 1; i <= n;i++) for(int j = 1; j<= m; j++) if(a[i][j+n] <= x) insert(i, j+n, 1); int flow = 0; while(bfs()) { flow += dfs(0, inf); } return flow == m; } int main() { cin >> n >> m >> mx; for(int i = 1; i <= n + m; i++) for(int j = 1; j<= n + m; j++) { cin >> a[i][j]; if(!a[i][j])a[i][j] = inf; } for(int k = 1; k < T; k++) for(int i = 1; i < T; i++) for(int j = 1; j < T; j++) a[i][j] = min(a[i][j], a[i][k] + a[k][j]); int l = 0, r = inf, ans = 0; while(l <= r) { int Mid = (l+r)>>1; if(check(Mid))ans = Mid, r = Mid -1; else l = Mid + 1; } cout << ans << endl; return 0; } |
这两个东西是等价的，而且最大字典序的拓扑序不需要考虑依赖关系
具体可以用反证法证明一下：
比如反图中有点6，链 4->5->3 …->8 ，（前面都比6小，最后一个比6大，如果链都比6小，先取显然不优），两种情况列出来会发现先6较优。
拓扑图是形如这样的链的拼接，也就是不可能先取拓扑图上的一部分再回来取编号最大的点。
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m,cnt,top; int last[100005],d[100005],ans[100005]; priority_queue<int,vector<int> >q; struct edge{ int to,next; }e[100005]; void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; } void solve(int x) { q.pop();ans[++top]=x; for(int i=last[x];i;i=e[i].next) { d[e[i].to]--; if(d[e[i].to]==0)q.push(e[i].to); } } int main() { T=read(); while(T--) { cnt=top=0; memset(last,0,sizeof(last)); memset(d,0,sizeof(d)); n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(v,u);d[u]++; } for(int i=1;i<=n;i++)if(!d[i])q.push(i); while(!q.empty()) solve(q.top()); if(top!=n)puts("Impossible!"); else { for(int i=n;i;i--) printf("%d ",ans[i],i==1?'\n':' '); puts(""); } } return 0; } |
「hdu2462」The Luckiest number
|
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 |
#include <set> #include <map> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long #define mod 2008 using namespace std; ll L, P, Q; ll phi(ll x) { ll ans = x; for(ll i = 2; i <= sqrt(x); i++) if(x % i == 0) { ans = ans / i * (i - 1); while(x % i == 0)x /= i; } if(x != 1)ans = ans / x * (x - 1); return ans; } ll qmul(ll a, ll b) { ll ans = 0; for(ll i = b; i; i >>= 1, a = (a + a) % L) if(i & 1)ans = (ans + a) % L; return ans; } ll qpow(ll a, ll b) { ll ans = 1; for(ll i = b; i; i >>= 1, a = qmul(a, a)) if(i & 1)ans = qmul(ans, a); return ans; } bool check(ll x) { return (qpow(10, x) == 1); } int main() { int cas = 0; while(cin >> L) { if(!L)break; cas++; printf("Case %d: ", cas); ll t = __gcd(L, 8LL); L = 9 * L / t; P = phi(L); if(__gcd(10LL, L) == 1) { ll ans = 0; for(ll i = 1; i <= sqrt(P); i++) if(P % i == 0) if(check(i)) { ans = i; break; } if(!ans) for(ll i = sqrt(P); i >= 1; i--) if(P % i == 0) if(check(P / i)) { ans = P / i; break; } cout << ans << endl; } else puts("0"); } return 0; } |
「bzoj3172」[Tjoi2013]单词
求出fail树后
对每个串的每个节点打标记
然后输出每个串终点子树的标记个数和
|
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<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; int n,pos[1000005]; struct acm{ int cnt; int next[1000005][26],sum[1000005],fail[1000005],q[1000005]; char ch[1000005]; acm(){ cnt=1; for(int i=0;i<26;i++)next[0][i]=1; } void insert(int &pos){ int now=1; scanf("%s",ch); int n=strlen(ch); for(int i=0;i<n;i++) { if(!next[now][ch[i]-'a'])next[now][ch[i]-'a']=++cnt; now=next[now][ch[i]-'a']; sum[now]++; } pos=now; } void buildfail(){ int head=0,tail=1; q[0]=1;fail[1]=0; while(head!=tail) { int now=q[head];head++; for(int i=0;i<26;i++) { int v=next[now][i]; if(!v)continue; int k=fail[now]; while(!next[k][i])k=fail[k]; fail[v]=next[k][i]; q[tail++]=v; } } for(int i=tail-1;i>=0;i--) sum[fail[q[i]]]+=sum[q[i]]; } }acm; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) acm.insert(pos[i]); acm.buildfail(); for(int i=1;i<=n;i++) printf("%d\n",acm.sum[pos[i]]); return 0; } |
Subscribe
计数器 9851229
OI 课件=>
OI 课件=>