又一个WordPress站点
sizeof(类型名字)
sizeof 表达式
得到指针本身所占空间的大小
得到被引用对象所占空间的大小
得到指针指向的对象所占的空间的大小，指针不需有效
得到整个数组所占空间的大小
只返回该类型固定部分的大小，不会计算对象中的元素占用了多少空间。
实测本机 sizeof(string)返回8，即便我把string初始化为一个很长的字符串，返回仍然是8。据说返回多少跟编译器和系统环境有关。vector同理。
函数传数组指针，在函数中sizeof数组指针，返回的是该指针本身所占空间的大小。
涉及到字节对齐
涉及到空类，虚函数
一棵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; } |
题目链接：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(); } } |
题目链接：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; } |
题目链接：http://poj.org/problem?id=1182
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 93015 | Accepted: 28066 |
Description
Input
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
|
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; } |
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6438
n(1<=n<=1e5)个城市连成的一条链，商品在第i个城市交易的价格为ai，你从第一个城市不回头的走到第n个城市，在每个城市你可以：
一开始你带着无限多的钱，并且你可以同时携带多个商品。
问你两个问题：
有点类似于网络流的反向边思想，这个之后再说。
思路：
跑一下样例。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; } |
|
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); } } |
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6319
一句话：取模是很耗时的，生成a[i]的时候，不需要因为防爆int而取模3次，大胆地爆int，反正还在longlong范围内，然后取模1次就OK，从4200MS降到了2400MS。
再加个取模优化和输入挂就更快了。（然而我的有限次地实验证再此题加输入优化是负优化）