作者：Logiko
【树】Red alert
一棵n节点的树，取三个节点，要求节点不在一条路径上，求取法总数。
竟然是一遍深搜O(n)大水题。
思路：不在一条路径的取法=总取法-在一条路径的取法=C(n,3)-?。
怎么求这个?呢。
画了图就懒得写字了，直接上程序。
|
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 |
#include<cstdio> #include<vector> using namespace std; #define ll long long const int maxn = 1e5+9; ll n; vector<int>e[maxn]; int siz[maxn]; ll ans; void dfs(int fa, int cur){ siz[cur]=1; for(int i=0; i<e[cur].size(); ++i){ int ne=e[cur][i]; if(ne==fa) continue; dfs(cur, ne); siz[cur]+=siz[ne]; } ll tot=0; for(int i=0; i<e[cur].size(); ++i){ int ne=e[cur][i]; if(ne==fa) continue; tot+=siz[ne]*(siz[cur]-1-siz[ne]); } ans+=(siz[cur]-1)*(n-siz[cur]); ans+=tot/2; } void solve(){ for(int i=0; i<=n; ++i){ e[i].clear(); } int u, v; for(int i=1; i<n; ++i){ scanf("%d%d", &u, &v); e[u].push_back(v); e[v].push_back(u); } ans=0; dfs(-1, 1); printf("%lld\n", n*(n-1)*(n-2)/3/2-ans); } int main(){ freopen("data.in", "r", stdin); freopen("B.out", "w", stdout); while(scanf("%lld", &n)!=EOF){ solve(); } return 0; } |
【POJ 2157】Maze
题目链接：http://poj.org/problem?id=2157
拿钥匙开门的迷宫搜索题，15年做的。
|
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 |
#include<cstdio> using namespace std; char g[24][24]; bool got[24][24]; int n, m, keysum[5], getkey[5], tx[4]={0, 0, -1, 1}, ty[4]={-1, +1, 0, 0}, doorsum[5]; bool ared[5]; int door[5][2], sx, sy, gx, gy; bool init() { int i, j; scanf("%d%d", &n, &m); if(0==n&&0==m) return false; for(i=1; i<=n; i++) { scanf("%s", &g[i][1]); } for(i=0; i<5; i++) keysum[i]=0; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { got[i][j]=false; if('a'<=g[i][j]&&g[i][j]<='e') { keysum[g[i][j]-'a']++; } else if('A'<=g[i][j]&&g[i][j]<='E') { doorsum[g[i][j]-'A']++; if(doorsum[g[i][j]-'A']==2) { printf("adfsdf"); return 0; } } else if('S'==g[i][j]) { sx=i; sy=j; } else if('G'==g[i][j]) { gx=i; gy=j; } } } for(i=0; i<5; i++) getkey[i]=0, ared[i]=false, doorsum[i]=0; return true; } void dfs(int x, int y) { bool is_door=false; got[x][y]=true; int key; if('a'<=g[x][y]&&g[x][y]<='e') { key=g[x][y]-'a'; getkey[key]++; if(ared[key]&&getkey[key]==keysum[key]) { dfs(door[key][0], door[key][1]); } } else if('A'<=g[x][y]&&g[x][y]<='F') { is_door=true; key=g[x][y]-'A'; door[key][0]=x; door[key][1]=y; ared[key]=true; } int i, nx, ny; for(i=0; i<4; i++) { nx=x+tx[i]; ny=y+ty[i]; if(1<=nx&&nx<=n&&1<=ny&&ny<=m) { if(got[nx][ny]) continue; if(g[nx][ny]=='X') continue; if(!is_door) { dfs(nx, ny); } else { key=g[x][y]-'A'; if(getkey[key]==keysum[key]) { dfs(nx, ny); } } } } } void solve() { dfs(sx, sy); if(got[gx][gy]) printf("YES\n"); else printf("NO\n"); } int main() { int i; while(init()) { solve(); } } |
【POJ 2992】Divisors
题目链接：http://poj.org/problem?id=2992
求C(n,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 62 63 64 65 66 67 68 |
// 2018/8/5 #include<cstdio> #include<cstring> using namespace std; #define ll long long #define maxn 439 #define prime_tot 89 int p[maxn], prime[prime_tot]; int prime_divisor[prime_tot]; ll ans[maxn][maxn]; void euler_prime_table(int n, int &tot, int p[], int prime[]){ tot=0; for(int i=1; i<=n; ++i){ p[i]=1; } p[1]=0; for(int i=2; i<=n; ++i){ if(p[i]){ p[i]=++tot; prime[tot]=i; } for(int j=1; j<=tot; ++j){ if(i*prime[j]>n){ break; } p[i*prime[j]]=0; if(0==i%prime[j]){ break; } } } } void add_divisor(int x, int tot, int num[], int direction){ for(int i=1; i<=tot&&prime[i]*prime[i]<=x; ++i){ while(0==x%prime[i]){ num[p[prime[i]]]+=direction; x/=prime[i]; } } if(x>1){ num[p[x]]+=direction; } } int main(){ int n, k, tot; euler_prime_table(maxn-1, tot, p, prime); for(n=0; n<=431; ++n){ memset(prime_divisor, 0, sizeof(prime_divisor)); ans[n][0]=1; for(k=1; k*2<=n; ++k){ ans[n][k]=1; add_divisor(n-k+1, tot, prime_divisor, 1); add_divisor(k, tot, prime_divisor, -1); for(int i=1; i<=tot; ++i){ if(prime_divisor[i]){ ans[n][k]*=(ll)(prime_divisor[i]+1); } } } } while(scanf("%d%d", &n, &k)!=EOF){ if(k*2>n){ k=n-k; } printf("%lld\n", ans[n][k]); } return 0; } |
【POJ 1182】【并查集】食物链
题目链接：http://poj.org/problem?id=1182
食物链
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 93015 | Accepted: 28066 |
Description
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
Input
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
Output
只有一个整数，表示假话的数目。
Sample Input
|
1 2 3 4 5 6 7 8 |
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 |
Sample Output
|
1 |
3 |
Source
题目大意：如题。
解法一：带权并查集。
解法二：用集合关系表示同类和捕食关系。
为了便于理解，这三类动物可以解释为分解者，消费者，生产者。
假设消费者捕食生产者，生产者捕食分解者，分解者捕食消费者。（实际上不是这样，这样说只是为了确立三者之间的捕食顺序关系）
n个动物，每个动物可能是三者之一，不妨用[1,n]表示分解者，[n+1, 2n]表示消费者，[2n+1,3n]表示生产者。
定义(a,b)表示动物a和b再同一个集合。
定义a,b为同类的集合关系表现为：(a,b)
定义a捕食b的集合关系表现为：(a,b+n)
定义merge(a,b)为使得a,b 在同一个集合
逐条读入k句话（排除掉显然错误的话），然后：
- 若断言a，b是同类。我们先判断a,b是否存在捕食或者反捕食关系：是否(a,b+n)和(b,a+n)由于我们不知道a，b是分解者，消费者还是生产者，但是我们知道a,b一定是同一种类型的。所以不妨认为：1，a,b都是分解者;2,a,b都是消费者,3,a,b都是生产者。
- 若断言a捕食b。我们要判断a,b是否是同类和b是否捕食a。
|
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 |
#include<cstdio> using namespace std; const int maxn = 5e4+9; int father[maxn*3]; int getfather(int a){ return father[a]==a?a:father[a]=getfather(father[a]); } void merge(int a, int b){ int root_a=getfather(a), root_b=getfather(b); father[root_b]=root_a; } int main(){ int n, k, ans=0; scanf("%d%d", &n, &k); for(int i=1; i<=3*n; ++i){ father[i]=i; } while(k--){ int D, x, y; scanf("%d%d%d", &D, &x, &y); if(x>n||y>n||(2==D&&x==y)){ ++ans; continue; } if(1==D){ if(getfather(x)==getfather(y+n)||getfather(y)==getfather(x+n)){ ++ans; } else{ merge(x, y); merge(x+n, y+n); merge(x+2*n, y+2*n); } } else{ if(getfather(x)==getfather(y)||getfather(x+n)==getfather(y)){ ++ans; } else{ merge(x, y+n); merge(x+n, y+2*n); merge(x+2*n, y); } } } printf("%d\n", ans); return 0; } |
HDU 6438 Buy and Resell
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6438
n(1<=n<=1e5)个城市连成的一条链，商品在第i个城市交易的价格为ai，你从第一个城市不回头的走到第n个城市，在每个城市你可以：
- 以ai的价格买入1个商品
- 以ai的价格卖出1个商品
- 什么也不做
一开始你带着无限多的钱，并且你可以同时携带多个商品。
问你两个问题：
- 最大收益
- 最大收益前提下的最小交易次数
有点类似于网络流的反向边思想，这个之后再说。
思路：
- 前提1：假如在一个城市既买入商品，又卖出商品，相当于什么也没做。所以从1到n讨论每个城市，我要做的是决策怎么交易：买，卖，不买不卖。
- 前提2：每走到一个城市，我都买商品，直到我走完所有城市，手上还有囤积的货物，说明当初这些货物本来不该购买。
- 前提3：收益=卖价和-买价和=累计收益+囤积货物成本
- 我的第一个想法是：讨论到第i个城市时，如果手里买价最低的商品（优先队列维护）价格低于ai时，我就卖出（累加收益），否则我就买入（累加成本）（因为我觉得既买又卖是没有意义的）。显然这是一个错误的算法，甚至连样例1都过不了。错在在第i个城市并不是该卖出商品的地方，说不定最优解并不是在第i个城市卖出商品呐。
- 我的第二个想法是：假如在第i个城市卖出商品获得一些收益，我还是要在第i个城市买入1个商品，说不定之后就能转手又赚一笔呐。显然这又是一个错误的算法，甚至还是连样例1都过不了。错在在第i个城市又买又买相当于什么也没做，说不定最优解是在第i个城市买入商品呐。
- 我的第三个想法是：假如在第i个城市卖出商品获得一些收益，我在第i个城市买2个商品。这样做的灵感源于网络流问题的反向边思想，在搜索的时候假如反向边，假如决策错误，可以在后面把这个错误决策抵消（反悔）掉。假如我在之后总共卖出了1个现在买入的商品，说明我在这个城市本来该不买也不卖，假如我在之后总共卖出了2个现在买入的商品，说明我在这个城市本来该买入1个商品，假如我在之后没有卖出任何现在买入的商品，说明我在这个城市本来该卖出1个商品。
跑一下样例。bought[i]表示最终在第i个城市买入的商品数量，值可能为0,1,2。sold[i]表示在第i个城市卖出的商品数量，值可能为0,1。
……（没图）
样例2过不了，我这样算出的交换次数是4，错误在于把既买入了9，又卖出了9，然而这两个9还不在同一个城市。我的解决方法是，在优先队列的比较函数上做文章。当两个城市的商品价格相同时，我优先选择卖出过商品的城市的商品（因为这样可以抵消交换次数）
然后我开心地写程序了：
|
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 |
#include<cstdio> #include<queue> using namespace std; #define ll long long const int MAXN = 1e5+9; ll a[MAXN]; int bought[MAXN], sold[MAXN]; struct cmp{ bool operator()(int i, int j){ if(a[i]!=a[j]){ return a[i]>a[j]; } else{ return sold[i]<sold[j]; } } }; priority_queue<int, vector<int>, cmp>q; void solve(){ int n; scanf("%d", &n); ll ans1=0; int ans2=0; for(int i=1; i<=n; ++i){ bought[i]=sold[i]=0; } for(int i=1; i<=n; ++i){ scanf("%lld", &a[i]); if(q.empty()){ q.push(i); ++bought[i]; ans1-=a[i]; } else{ int top=q.top(); if(a[i]>a[top]){ ++sold[i]; ans1+=a[i]; q.pop(); ans1-=2*a[i]; bought[i]+=2; q.push(i); q.push(i); } else{ ++bought[i]; ans1-=a[i]; q.push(i); } } } while(!q.empty()){ int cur=q.top(); ans1+=a[cur]; --bought[cur]; q.pop(); } for(int i=1; i<=n; ++i){ ans2+=max(bought[i], sold[i])-min(bought[i], sold[i]); } printf("%lld %d\n", ans1, ans2); } int main(){ int T; scanf("%d", &T); while(T--){ solve(); } return 0; } |
然后WA了……。
错误数据为：
|
1 2 3 |
1 7 10 6 6 8 8 10 9 |
正解为 7 4
我输出 7 6。
问题处在计算最小交换次数上。
输出中间结果
……（没图）
发现这组数据中两个8各卖出1次商品，买入2次商品，然而到达价格10，9两个城市后，都选择了卖出第2各8的商品。正确的选择方法显然是再两个8各买一次商品，抵消掉两个8买入的商品，交换次数为4。然而我这样抵消不了，所有输出6。
考虑为什么发生这种情况，回想之前买入两个商品的原因，就是为了提供一个挽回的途径，但仔细一想，其实这两个商品本质上的意义是有区别的。 也就是之前说的：
假如我在之后总共卖出了1个现在买入的商品，说明我在这个城市本来该不买也不卖，假如我在之后总共卖出了2个现在买入的商品，说明我在这个城市本来该买入1个商品，假如我在之后没有卖出任何现在买入的商品，说明我在这个城市本来该卖出1个商品。
所以考虑标记区分这两个商品，添加一个formiko变量（值为1或2）标记这个商品的种类。之后卖出一个现在买入的商品，会抵消两次交易次数，所以我们把其中一个商品的formiko赋值为2，其他所有商品的formiko赋值为1。
这样，这组样例中，就能分别买入两个8的一个商品，抵消掉多余的交换次数。
以下是AC程序。
|
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 |
#include<cstdio> #include<queue> using namespace std; #define ll long long const int MAXN = 1e5+9; ll a[MAXN]; int bought[MAXN], sold[MAXN]; struct node{ int id, formiko; }; struct cmp{ bool operator()(node x, node y){ if(a[x.id]!=a[y.id]){ return a[x.id]>a[y.id]; } else{ return x.formiko<y.formiko; } } }; priority_queue<node, vector<node>, cmp>q; void solve(){ int n; scanf("%d", &n); ll ans1=0; int ans2=0; for(int i=1; i<=n; ++i){ bought[i]=sold[i]=0; } for(int i=1; i<=n; ++i){ scanf("%lld", &a[i]); if(q.empty()){ q.push((node){i, 1}); ++bought[i]; ans1-=a[i]; } else{ int top=q.top().id; if(a[i]>a[top]){ ++sold[i]; ans1+=a[i]; q.pop(); ans1-=2*a[i]; bought[i]+=2; q.push((node){i, 1}); q.push((node){i, 2}); } else{ ++bought[i]; ans1-=a[i]; q.push((node){i, 1}); } } } while(!q.empty()){ int cur=q.top().id; ans1+=a[cur]; --bought[cur]; q.pop(); } for(int i=1; i<=n; ++i){ ans2+=max(bought[i], sold[i])-min(bought[i], sold[i]); } printf("%lld %d\n", ans1, ans2); } int main(){ int T; scanf("%d", &T); while(T--){ solve(); } return 0; } |
【模板】makedata
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include<cstdio> #include<ctime> #include<cstdlib> using namespace std; const int MAXN = 1e6+9; const int MAXM = 1e6+9; int main(){ srand(time(NULL)); int T=rand()%10+1; printf("%d\n", T); while(T--){ int n=rand()%(MAXN-1)+1; printf("%d\n", n); } return 0; } |
【模板】树状数组
单点更新，区间查找
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int lowbit(int x){ return x&(-x); } int sum(int x){ int ret=0; while(x>0){ ret+=C[x]; x-=lowbit(x); } return ret; } void add(int x, int d, int n){ while(x<=n){ C[x]+=d; x+=lowbit(x); } } |
【卡常】Ascending Rating
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6319
一句话：取模是很耗时的，生成a[i]的时候，不需要因为防爆int而取模3次，大胆地爆int，反正还在longlong范围内，然后取模1次就OK，从4200MS降到了2400MS。
再加个取模优化和输入挂就更快了。（然而我的有限次地实验证再此题加输入优化是负优化）