作者: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
现有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
以下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
- 若断言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。
再加个取模优化和输入挂就更快了。(然而我的有限次地实验证再此题加输入优化是负优化)