一道图论神题(god)
Time Limit:1000ms Memory Limit:128MB
题目描述
LYK有一张无向图G={V,E}，这张无向图有n个点m条边组成。并且这是一张带权图，只有点权。
LYK想把这个图删干净，它的方法是这样的。每次选择一个点，将它删掉，但删这个点是需要代价的。假设与这个点相连的还没被删掉的点是u1,u2,…,uk。LYK将会增加a[u1],a[u2],…,a[uk]的疲劳值。
它想将所有点都删掉，并且删完后自己的疲劳值之和最小。你能帮帮它吗？
输入格式(god.in)
第一行两个数n,m表示一张n个点m条边的图。
第二行n个数ai表示点权。
接下来m行每行三个数u,v，表示有一条连接u,v的边。数据保证任意两个点之间最多一条边相连，并且不存在自环。
输出格式(god.out)
你需要输出这个最小疲劳值是多少。
输入样例
4 3
10 20 30 40
1 4
1 2
2 3
输出样例
40
样例解释
一个合理的方法是先删4号点，此时有10点疲劳值。接下来删3号点，获得20点疲劳值，再删2号点，获得10点疲劳值，最后删1号点，没有疲劳值。总计40点疲劳值。
对于30%的数据n<=10。
对于60%的数据n,m<=1000。
对于100%的数据1<=n,m,ai<=100000
思路：贪心，一遍AC。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #define MAXN 101000 using namespace std; map<int,int>ma[MAXN]; int n,m,tot,cap[MAXN]; long long ans; int to[MAXN*2],net[MAXN*2],head[MAXN*2]; struct nond{ int val,id; }v[MAXN]; int cmp(nond a,nond b){ return a.val>b.val; } void add(int u,int v){ to[++tot]=v;net[tot]=head[u];head[u]=tot; to[++tot]=u;net[tot]=head[v];head[v]=tot; } int main(){ freopen("god.in","r",stdin); freopen("god.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&v[i].val); v[i].id=i; cap[i]=v[i].val; } sort(v+1,v+1+n,cmp); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); ma[u][v]=1; ma[v][u]=1; } for(int i=1;i<=n;i++){ for(int j=head[v[i].id];j;j=net[j]) if(ma[v[i].id].find(to[j])!=ma[v[i].id].end()){ ans+=cap[to[j]]; ma[to[j]].erase(v[i].id); } } cout<<ans; } /* 4 3 10 20 30 40 1 4 1 2 2 3 */
位运算2(bit)
Time Limit:1000ms Memory Limit:128MB
题目描述
LYK拥有一个十进制的数N。它赋予了N一个新的意义：不考虑N的符号，将N每一位都拆开来后再加起来就是N所拥有的价值。例如数字123拥有6的价值，数字999拥有27的价值，数字-233拥有8的价值。
假设数字N的价值是K，LYK想找到一个价值是K+1的数字，当然这个答案实在太多了，LYK想使得这个价值为K+1的数字尽可能大，并且需要保证这个数字小于N。
输入格式(bit.in)
一个整数N。
输出格式(bit.out)
一个数表示答案。你需要输出一个整数，且这个数不包含前导0。
输入样例1
199
输出样例1
-299
输入样例2
1520
输出样例2
1512
对于20%的数据|N|<=10
对于40%的数据|N|<=100
对于60%的数据|N|<=10^9
对于80%的数据|N|<=10^1000
对于100%的数据|N|<=10^100000。
思路：大模拟，有三种情况没有考虑，挂掉了3个点。
~~~~(>_<)~~~~ 改不过来了90分代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; char n[100100]; int len; int num[100100],tmp[100100],ans[100100]; int main(){ freopen("bit.in","r",stdin); freopen("bit.out","w",stdout); int cnt=0,flag=0,flag1=0; scanf("%s",n); len=strlen(n); if(n[0]!='-'){ for(int i=0;i<len;i++){ num[i+1]=n[i]-'0'; tmp[i+1]=num[i+1]; } if(len!=1){ if(num[len]<=7&&num[len-1]>=1){ int y=0; num[len-1]-=1;num[len]+=2; while(num[y]==0) y++; for(int i=y;i<=len;i++) cout<<num[i]; return 0; } else if(num[len]>7&&num[len-1]>=1){ if(num[len-2]!=0){ int bns=9-num[len-1]-2,y=1; num[len-2]-=1; num[len-1]=9; num[len]-=bns; while(num[y]==0) y++; for(int i=y;i<=len;i++) ans[++cnt]=num[i]; } else{ int x=2,y=1; int bns=9-num[len-1]-2; while(!num[len-x]&&len!=2) x++; num[len-x]-=1; num[len-x+1]=9; num[len-x+2]=num[len]-bns; while(num[y]==0) y++; for(int i=y;i<=len-x+2;i++) ans[++cnt]=num[i]; for(int i=len-x+3;i<=len;i++) ans[++cnt]=0; } for(int i=1;i<=cnt;i++) if(ans[i]>=10||ans[i]<0) flag=1; if(len==cnt) for(int i=1;i<=cnt;i++) if(ans[i]>tmp[i]){ flag=1; break; } else if(ans[i]<tmp[i]) break; if(flag){ cout<<"-"; for(int i=len;i>=1;i--) if(tmp[i]!=9){ flag1=1; tmp[i]+=1; break; } if(!flag1) tmp[0]+=1; } if(!flag) for(int i=1;i<=len;i++) cout<<ans[i]; if(flag&&flag1) for(int i=1;i<=len;i++) cout<<tmp[i]; else if(flag&&!flag) for(int i=0;i<=len;i++) cout<<tmp[i]; return 0; } else if(num[len]<=7&&num[len-1]<1){ int x=1,y=1; while(!num[len-x]) x++; num[len-x]-=1; num[len-x+1]=num[len]+2; while(num[y]==0) y++; for(int i=1;i<=len-x+1;i++) cout<<num[i]; for(int i=len-x+2;i<=len;i++) cout<<"0"; return 0; } } else{ cout<<"-"<<num[1]+1; return 0; } } else{ len-=1; for(int i=1;i<=len;i++){ num[i]=n[i]-'0'; tmp[i]=num[i]; } for(int i=len;i>=1;i--) if(tmp[i]!=9){ flag1=1; tmp[i]+=1; break; } if(!flag1) tmp[0]+=1; cout<<"-"; if(flag1) for(int i=1;i<=len;i++) cout<<tmp[i]; else for(int i=0;i<=len;i++) cout<<tmp[i]; return 0; } }
这是标程：
#include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #include <string> #include <cstring> using namespace std; char s[100005]; int len,sum,i,j,FLAG; int main() { freopen("bit.in","r",stdin); freopen("bit.out","w",stdout); scanf("%s",s); FLAG=0; if (s[0]!='-') { len=strlen(s); sum=0; for (i=len-1; i>=0; i--) { if (s[i]>='1' && sum>=2) { s[i]=char(s[i]-1); sum=2; for (j=i+1; j<len; j++) { while (sum && s[j]<'9') { sum--; s[j]=char(s[j]+1); } } int SS=0; for (j=i+1; j<len; j++) SS+=s[j]-'0'; for (j=i+1; j<len; j++) { if (SS>=9) {s[j]='9'; SS-=9;} else {s[j]=char(SS+'0'); SS=0;} } FLAG=1; break; } sum+='9'-s[i]; } if (FLAG) { for (i=0; i<len; i++) if (s[i]!='0') break; for (j=min(len-1,i); j<len; j++) cout<<s[j]; cout<<endl; return 0; } cout<<'-'; for (i=len-1; i>=0; i--) { if (s[i]<'9') { s[i]=char(s[i]+1); FLAG=1; break; } } if (FLAG) { for (i=0; i<len; i++) if (s[i]!='0') break; for (j=min(len-1,i); j<len; j++) cout<<s[j]; cout<<endl; return 0; } cout<<1; for (i=0; i<len; i++) if (s[i]!='0') break; for (j=min(len-1,i); j<len; j++) cout<<s[j]; cout<<endl; return 0; } FLAG=0; cout<<'-'; len=strlen(s); for (i=len-1; i>=1; i--) { if (s[i]<'9') { s[i]=char(s[i]+1); FLAG=1; break; } } if (FLAG) { for (i=1; i<len; i++) if (s[i]!='0') break; for (j=min(len-1,i); j<len; j++) cout<<s[j]; cout<<endl; return 0; } cout<<1; for (i=1; i<len; i++) if (s[i]!='0') break; for (j=min(len-1,i); j<len; j++) cout<<s[j]; cout<<endl; return 0; }
逆序对(pair)
Time Limit:1000ms Memory Limit:128MB
题目描述
LYK最近在研究逆序对。
这个问题是这样的。
一开始LYK有一个2^n长度的数组ai。
LYK有Q次操作，每次操作都有一个参数k。表示每连续2^k长度作为一个小组。假设n=4,k=2，则a[1],a[2],a[3],a[4]为一个小组，a[5],a[6],a[7],a[8]为一个小组，a[9],a[10],a[11],a[12]为一个小组，a[13],a[14],a[15],a[16]也为一个小组。
然后LYK对于每个小组都翻转，也就是说原数组会变成a[4],a[3],a[2],a[1],a[8],a[7],a[6],a[5],a[12],a[11],a[10],a[9],a[16],a[15],a[14],a[13]。之后它想求出这2^n个数的逆序对是多少。
因此你需要输出对于每次操作，操作完后这2^n个数的逆序对有多少对。
两个数ai,aj被称为逆序对当且仅当i<j且ai>aj。
输入格式(pair.in)
第一行一个数n。
接下来一行2^n个数ai表示一开始的数组。
接下来一行一个数Q，表示操作的次数。
接下来一行Q个数，表示每次操作的参数k。
输出格式(pair.out)
Q行，表示每次操作后的答案。
输入样例
2
2 1 4 3
4
1 2 0 2
输出样例
0
6
6
0
样例解释
第一次操作，{2,1,4,3}->{1,2,3,4}
第二次操作，{1,2,3,4}->{4,3,2,1}
第三次操作，{4,3,2,1}->{4,3,2,1}
第四次操作，{4,3,2,1}->{1,2,3,4}
对于30%的数据n<=10，Q<=10。
对于50%的数据n<=10，Q<=1000。
对于80%的数据n<=10，Q<=200000。
对于100%的数据n<=17，Q<=200000，1<=ai<=2^n。
思路：
例：1 2 3 4 5 6 7 8 k=3
翻转结果为 8 7 6 5 4 3 2 1
翻转过程可以拆分为：
第一步： 2 1 4 3 6 5 8 7
第二步：4 3 2 1 8 7 6 5
第三步：8 7 6 5 4 3 2 1
所以每一次翻转都可以拆分，而拆分的过程就是交换相邻的2^(步数-1）
所以归并排序求逆序对的时候，用st表维护从第i个位置，长为2^j的区间的逆序对个数
然后求出对应区间的顺序对个数
维护所有长为2^i的区间的逆序对个数rev[i]和顺序对个数pos[i]
统计答案的时候，拆分就是swap（rev，pos）
在这里顺序对个数是用总个数-逆序对个数求的
所以就会有一个问题，例：
2 2 3 3
实际上的：
pos ： 0 0
rev ： 0 0
但求的时候，pos ：2 4
因为用总个数-逆序对个数=顺序对个数+相等的数对
所以归并过程中，还要预处理从第i个位置，长为2^j的区间的相等数对个数
计算rev，pos时，同时计算same[i]，表示所有长为2^i的区间相等的数对个数
求解的时候 先swap（rev，pos），然后rev-=same，再 pos=总的-rev
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=(1<<17)+5; int n,T,PP,now,A,sum,o; int p[N],a[N],b[N],RR[N]; long long t[105],TT[105]; long long st[N][20],ST[N][20]; void pre(int l,int r){ if(l==r) return; int mid=(l+r)/2; pre(l,mid); pre(mid+1,r); int i=l,j=mid+1,o=l; for(i=l;i<=r;i++) b[i]=a[i]; for(i=r;i>=mid;i--){ RR[i]=i; if(i!=r&&b[i+1]==b[i]) RR[i]=RR[i+1]; } i=l;j=mid+1; while(i<=mid&&j<=r){ if(b[i]<=b[j]){ a[o++]=b[i]; if(b[i]==b[j]) ST[l][p[r-l+1]]+=RR[j]-j+1; i++; } else{ a[o++]=b[j]; st[l][p[r-l+1]]+=mid-i+1; j++; } } if(i<=mid) for(j=i;j<=mid;j++) a[o++]=b[j]; else if(j<=r) for(i=j;i<=r;i++) a[o++]=b[i]; } int main(){ freopen("pair.in","r",stdin); freopen("pair.out","w",stdout); scanf("%d",&n); sum=(1<<n); for(int i=1;i<=sum;i++) scanf("%d",&a[i]); for(int i=1;i<=17;i++) p[1<<i]=i; pre(1,sum); for(int i=1;i<=n;i++) for(int j=1;j<=(1<<n);j+=(1<<i)){ t[i]+=st[j][i]; TT[i]+=ST[j][i]; } scanf("%d",&T); while(T--){ long long ans=0;int Q; scanf("%d",&Q); for(int i=1;i<=Q;i++) t[i]=1ll*(1<<i-1)*(1<<i-1)*(1<<n-i)-TT[i]-t[i]; for(int i=1;i<=n;i++) ans+=t[i]; printf("%I64d ",ans); } return 0; }