A. Valera and Antique Items
题目大意:有一场拍卖,有n个卖家,每个卖家有ki个物品并且底价知道,你想买东西并且只有Ｖ元钱，问可以从哪几个商家那里去买
思路:对每个卖家的每样商品作比较即可
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define maxn 1000 5 using namespace std; 6 int ans[maxn],h,x,k; 7 int main() 8 { 9 int n,v; 10 scanf("%d%d",&n,&v); 11 for(int i=1;i<=n;i++) 12 { 13 scanf("%d",&k); 14 int flag=0; 15 for(int j=1;j<=k;j++) 16 { 17 scanf("%d",&x); 18 if(x<v && flag==0)ans[++h]=i,flag=1; 19 } 20 } 21 printf("%d ",h); 22 for(int i=1;i<=h;i++)printf("%d ",ans[i]); 23 return 0; 24 }
B. Valera and Fruits
题目大意:你有n棵果树,每颗果树只能在ai ,a(i+1)两天时间内进行采摘，并且有bi个果子,你每天只能摘v个果子，问最多能摘多少果子？
思路:记录下每天有多少果子，显然在还能摘的前提下先摘昨天的最优，然后贪心即可
1 #include<cstdio> 2 #include<algorithm> 3 #define maxn 10000 4 using namespace std; 5 struct T 6 { 7 int x;int y; 8 }a[maxn]; 9 int cmp(T a ,T b) 10 { 11 return a.x<b.x; 12 } 13 int day[maxn]; 14 int main() 15 { 16 int n,v; 17 scanf("%d%d",&n,&v); 18 for(int i=1;i<=n;i++) 19 { 20 scanf("%d%d",&a[i].x,&a[i].y); 21 day[a[i].x]+=a[i].y; 22 } 23 int ans=0; 24 for(int i=1;i<=3009;i++) 25 { 26 if(v<=day[i-1]) 27 { 28 ans+=v; 29 } 30 else 31 { 32 ans+=day[i-1]; 33 int u=v-day[i-1]; 34 if(day[i]>=u) 35 { 36 day[i]-=u; 37 ans+=u; 38 } 39 else 40 { 41 ans+=day[i]; 42 day[i]=0; 43 } 44 } 45 } 46 printf("%d ",ans); 47 return 0; 48 }
C. Valera and Tubes
题目大意:你有一个N*M的棋盘放管子，每个管子至少覆盖两个ceil，要你给出一个不重不漏的覆盖满整个棋盘并且恰好只有k个管子的方案
思路:我先蛇形的放一个长长的管子,然后进行分割每次分割一个长度为２的管子即可
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int dir=1,x=1,y=0,n,m,r; 5 int next() 6 { 7 if(dir==1) 8 { 9 if(y==m)x++,dir--;else 10 y++; 11 } 12 else 13 { 14 if(y==1)x++,dir++;else y--; 15 } 16 printf("%d %d ",x,y); 17 } 18 int main() 19 { 20 scanf("%d%d%d",&n,&m,&r); 21 for(int i=1;i<r;i++) 22 { 23 printf("2 ");next();next(); 24 puts(""); 25 } 26 printf("%d ",n*m-(r-1)*2); 27 for(int i=1;i<=n*m-(r-1)*2;i++)next(); 28 return 0; 29 }
D. Valera and Swaps
题目大意:你有一个n个元素的排列p，定义f（ｐ）是最少的使p变成 1 2 3 4 5....形式排列的交换次数,给你一个数字k，要你给出最少的交换方案,使得ｐ变成q并且f(q)=k,多个方案满足时用交换方案字典序最小的
思路:有了思维定势:只能交换相邻元素的排列要逆序数上想,能交换任意两个元素的要往置换群上想,然后置换群显然需要分解成n个轮换的乘积,一个k轮换显然需要交换k-1次才能归位,然后发现假设能分解成m个轮换,那需要交换的次数为n-m，交换一个轮换内的元素会使轮换个数＋１，交换不同轮换内的元素会使轮换个数－１,想到了这些便可以瞎搞了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define maxn 10000 5 using namespace std; 6 int visit[maxn],p[maxn],kk; 7 int dfs(int k,int ini) 8 { 9 if(k!=ini && k-ini<=kk-ini)kk=k; 10 if(visit[k]==1)return k-1; 11 visit[k]=1; 12 return dfs(p[k],ini); 13 } 14 int main() 15 { 16 int n,ans=0,k; 17 scanf("%d",&n); 18 for(int i=1;i<=n;i++) 19 { 20 scanf("%d",&p[i]); 21 } 22 scanf("%d",&k); 23 int cir=0; 24 for(int i=1;i<=n;i++) 25 { 26 if(!visit[i])dfs(i,i),cir++; 27 } 28 if(n-cir==k) 29 { 30 puts("0"); 31 } 32 else if(n-cir<k)//add repeted 33 { 34 printf("%d ",k-n+cir); 35 for(int i=1;i<=k-n+cir;i++) 36 { 37 memset(visit,0,sizeof(visit)); 38 dfs(1,1); 39 int j; 40 for(j=1;j<=n;j++) 41 { 42 if(!visit[j])break; 43 } 44 swap(p[1],p[j]); 45 printf("1 %d ",j); 46 } 47 } 48 else 49 { 50 printf("%d ",n-k-cir); 51 for(int i=1;i<=n-k-cir;i++) 52 { 53 memset(visit,0,sizeof(visit)); 54 int ans=0,j; 55 for(j=1;j<=n;j++) 56 { 57 kk=0x3f3f3f3f; 58 if(p[j]!=j) 59 { 60 int kk=0x3f3f3f3f; 61 dfs(j,j); 62 break; 63 } 64 } 65 swap(p[j],p[kk]); 66 printf("%d %d ",j,kk); 67 } 68 } 69 return 0; 70 }