每日一练
2.22
Problem A MUH and Important Things
题意：给出一列数 a[i]，输出三种不同的升序排列的方式
简析：记录下值相等的位置，如果<=1，就不能构成，然后每次输出，交换一个
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<queue> 9 #include<algorithm> 10 #define mod=1e9+7; 11 using namespace std; 12 13 typedef long long LL; 14 const int maxn=2000+5; 15 int b[maxn]; 16 17 struct node{ 18 int h; 19 int pos; 20 } a[maxn]; 21 22 int cmp(node n1,node n2){ 23 if(n1.h!=n2.h) return n1.h<n2.h; 24 return n1.pos<n2.pos; 25 } 26 27 int main(){ 28 int n,i,j,cnt; 29 cin>>n; 30 for(i=1;i<=n;i++){ 31 cin>>a[i].h; 32 a[i].pos=i; 33 } 34 35 sort(a+1,a+n+1,cmp); 36 cnt=0; 37 38 for(i=2;i<=n;i++){ 39 if(a[i].h==a[i-1].h){ 40 b[cnt++]=i-1; 41 } 42 } 43 if(cnt<=1) printf("NO\n"); 44 else{ 45 printf("YES\n"); 46 for(i=1;i<n;i++) 47 printf("%d ",a[i].pos); 48 printf("%d\n",a[i].pos); 49 50 swap(a[b[0]],a[b[0]+1]); 51 52 for(i=1;i<n;i++) 53 printf("%d ",a[i].pos); 54 printf("%d\n",a[i].pos); 55 56 // swap(a[b[0]],a[b[0]+1]); 57 swap(a[b[1]],a[b[1]+1]); 58 59 for(i=1;i<n;i++) 60 printf("%d ",a[i].pos); 61 printf("%d\n",a[i].pos); 62 } 63 return 0; 64 }
Problem B MUH and House of Cards
题意：给出 n 张牌,求恰好可以用这n张牌搭成多少个不同高度的房子
简析：可以算出高度 为 n 的房子至少需要的牌为 n*2 +(n-1) + (n-1)*2 +(n-2) + ...+1*2 +0
化简就是 (3n*n+n)/2，又因为搭成一个房间需要3张牌，所以最后剩下的判断是否能够整除3，再搭在第一层就可以了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<queue> 9 #include<algorithm> 10 #define mod=1e9+7; 11 using namespace std; 12 13 typedef long long LL; 14 LL n; 15 LL ans,tmp,row,sum=0; 16 17 int main(){ 18 cin>>n; 19 for(LL i=1;(tmp=(3*i+1)*i/2)<=n;i++){ 20 21 if((n-tmp)%3==0) 22 ans++; 23 } 24 cout<<ans<<"\n"; 25 return 0; 26 }
bonus 字符串专题
2.22
你需要一个KMP的模板。
原文：http://www.cnblogs.com/chdacm/p/5208119.html
