模拟
开个struct排序即可 c++吼啊
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=100010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 struct stu{ 17 int ch,ma,en; 18 int tot; 19 int id; 20 }s[300]; 21 int cmp(stu a,stu b){ 22 if(a.tot!=b.tot)return a.tot>b.tot; 23 if(a.ch!=b.ch)return a.ch>b.ch; 24 return a.id<b.id; 25 } 26 int n; 27 int main(){ 28 n=read(); 29 int i,j; 30 for(i=1;i<=n;i++){ 31 s[i].ch=read();s[i].ma=read();s[i].en=read(); 32 s[i].tot=s[i].ch+s[i].en+s[i].ma; 33 s[i].id=i; 34 } 35 sort(s+1,s+n+1,cmp); 36 for(i=1;i<=5;i++){ 37 printf("%d %d ",s[i].id,s[i].tot); 38 } 39 return 0; 40 }
贪心
价值从小到大排序。每次把最大的和最小的组合在一起（如果不能组合，那么最大的单独成为一组）
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=30010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 int w,n; 17 int p[mxn]; 18 int main(){ 19 w=read();n=read(); 20 int i,j; 21 for(i=1;i<=n;i++) p[i]=read(); 22 sort(p+1,p+n+1); 23 int hd=1,tl=n; 24 int cnt=0; 25 while(hd<=tl){ 26 if(p[hd]+p[tl]<=w)cnt++,hd++,tl--; 27 else tl--,cnt++; 28 } 29 printf("%d ",cnt); 30 return 0; 31 }
DP
能闪则闪。不能闪的时候，同时处理原地回蓝和一直跑两个状态，如果回蓝后闪烁比跑的距离更远，就更新距离。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=100010; 10 int m,s,t; 11 int main(){ 12 scanf("%d%d%d",&m,&s,&t); 13 int i,j; 14 int now=0; 15 int tst=0; 16 for(i=1;i<=t;i++){ 17 if(m>=10){ 18 tst+=60; 19 m-=10; 20 } 21 else m+=4; 22 if(tst>now+17)now=tst; 23 else now+=17; 24 if(now>=s)break; 25 } 26 if(i>t)printf("No %d ",now); 27 else printf("Yes %d ",i); 28 return 0; 29 }
普通的汉诺塔方案数是f(n)=2^n-1
这里因为两个盘等价，方案数直接乘2变成2^(n+1)-2
一个高精乘单精就可以解决，之后末尾直接-2 （因为2的次方数，个位只能是2 4 6 8的一种，所以不需要借位）
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=10001; 10 int len=1; 11 int a[mxn]; 12 int main(){ 13 int i,j,n; 14 scanf("%d",&n); 15 a[1]=1; 16 for(i=0;i<=n;i++){ 17 for(j=len;j;j--){ 18 a[j]*=2; 19 a[j+1]+=a[j]/10; 20 a[j]%=10; 21 } 22 if(a[len+1]) ++len; 23 } 24 a[1]-=2; 25 for(i=len;i;i--)printf("%d",a[i]); 26 printf(" "); 27 return 0; 28 }