这还是没有考什么几何题物理题，要是考了，岂不完蛋？
代码奇丑无比。。
A: 哦吼？GJC要防AK了？
如果x是y的倍数输出-1，否则输出x。
#include<cstdio>
#include<cctype>
#include<vector>
#include<iostream>
using namespace std;
int x,y;
int main()
{
scanf("%d%d",&x,&y);
if(x%y==0)printf("-1\n");
else printf("%d\n",x);
return 0;
} B: 730的天花板
斐波那契变形。对于3*n的矩阵，考虑最左边的一列，只有两种选择，要么放2*2的，要么不放。设f（k）为3*k矩阵方案数，如果最左边放2*2，则占了两行，剩下两个位只能放2个1*1的，方案数2*f（n-2），如果不放2*2的，就是只放1*1的，只能放3个1*1的，方案数f（n-1）.故递推公式f（n）=f（n-1）+2*f（n-2）.递推边界f（1）=f（0）=1。
#include<cstdio>
#include<cctype>
#include<vector>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n,a,b,c;
int f[10000005];
int main()
{
scanf("%d",&t);
f[0]=f[1]=1;
for(int i=2;i<=10000000;i++)f[i]=(f[i-1]+2*f[i-2])%19260817;
while(t--)
{
scanf("%d",&n);
printf("%d\n",f[n]);
}
return 0;
} C: gugugu
模拟
#include<cstdio>
#include<cctype>
using namespace std;
int t,n;
char s[1005];
bool ok(int n)
{
if(n<=1)return 0;
for(int i=2;i<=n-1;i++)if(n%i==0)return false;
return true;
}
int main()
{
scanf("%d",&t);
int cnt=0;
while(t--)
{
scanf("%s",s);
for(int i=0;s[i];i++)if(tolower(s[i])=='g'&&tolower(s[i+1])=='u')cnt++;
}
printf(ok(cnt)?"gugugu\n":"gu\n");
return 0;
} D: 不可思议唤来不可思议β
排列组合题，显然枚举会超时。比赛时思路是对的，但是忘了含有重复元素的排列数怎么算，使劲推公式，没有思路，无果，，回来一查，这不是高中数学排列组合裸题吗！
假设有 111223这6个数，如何计算它的全排列呢？先假设这6个数字都不相同，排列共A(6,6)种，但在这A(6,6)种排列中，3个1和2个2是一样的，但被计算了A(3,3),A(2,2)种，因此答案就是A(6,6)/A(3,3)/A(2,2)种，这就是这道题最关键的地方。
先考虑最左边那一位可以填1，2，3三种，可以确定全排列中最高位分别为1，2，3时排列的个数，设排列总数为x，则最高位的数字可以确定加起来等于x*10^5，其实全排列先考虑哪一个位都是一样的，其他每一位都可以这样考虑，结果就是x*10^5+x*10^4+x*10^3+x*10^2+x*10+x.
这个x又怎么确定呢？当填1时排列数为1*（11223的全排列数），填2时排列数为2*（11123的全排列数），填3时排列数为3*（11122的全排列数），就是这样的思路。
下来写时候一处从0开始脑抽写出1开始，找不出错，然后花好多时间和next_permutation对拍才找出来错误。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,num[10];
long long fact[10],ans;
int main()
{
//freopen("input.in","r",stdin);
fact[0]=fact[1]=1;
for(int i=2;i<10;i++)fact[i]=fact[i-1]*i;
while(scanf("%d",&n)&&n)
{
memset(num,0,sizeof(num));
ans=0;
for(int i=0,k;i<n;i++)
{
scanf("%d",&k);
num[k]++;
}
long long cnt=0,pos;
for(int i=0;i<10;i++)if(num[i])
{
pos=i*fact[n-1];
for(int j=0;j<10;j++)
{
if(i==j)pos/=fact[num[j]-1];
else pos/=fact[num[j]];
}
cnt+=pos;
}
for(int i=0;i<n;i++)ans=ans*10+cnt;
printf("%lld\n",ans);
}
return 0;
} E: Hacking to the Gate
导数用等价无穷小代换得到1.
F: 维生素
开始想的搜索剪枝，差不多写完才发现就是一个相当水的贪心。。只有5种搭配，记录7个价格就行了。记录a，b，c分别的最低价钱3个最低价钱，abc任意搭配2种在同一个药里的3个最低价钱，abc均含在同一个药里的最低价钱，共7给价钱。搭配的话单买abc1种，一种单一种双3种，abc一块买1种，共5种。注意（ab，bc）买这两个药归在了a+bc或者ab+c里，因为a保存的是含有a元素的药的最低价钱，其他价钱也是一样的道理，容易想象，这是正确的。
#include<cstdio>
#include<cctype>
#include<vector>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n;
vector<int> have[3];
int x;
char s[105];
int num[3];
int money[200];
int main()
{
//freopen("input.in","r",stdin);
scanf("%d",&t);
while(t--)
{
for(int i=0;i<200;i++)money[i]=(1<<25);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=0;j<3;j++)num[j]=0;
scanf("%d%s",&x,s);
for(int j=0;s[j];j++)num[s[j]-'A']=1;
if(num[0]==1)money[0]=min(money[0],x);
if(num[1]==1)money[1]=min(money[1],x);
if(num[2]==1)money[2]=min(money[2],x);
if(num[0]==1&&num[1]==1)money[3]=min(money[3],x);
if(num[1]==1&&num[2]==1)money[4]=min(money[4],x);
if(num[0]==1&&num[2]==1)money[5]=min(money[5],x);
if(num[0]==1&&num[1]==1&&num[2]==1)money[6]=min(money[6],x);
}
bool ok=1;
for(int j=0;j<=2;j++)if(money[j]==(1<<25))ok=0;
if(!ok)printf("-1\n");
else
{
int ans=(1<<30);
ans=min(ans,money[0]+money[1]+money[2]);
ans=min(ans,money[3]+money[2]);
ans=min(ans,money[4]+money[0]);
ans=min(ans,money[5]+money[1]);
ans=min(ans,money[6]);
printf("%d\n",ans);
}
}
return 0;
} G: 你选择的这个世界
比赛时一直想着什么欧拉函数，很复杂，，结果那么多人过？？回来经提醒，打表找规律，结果就是平方数嘛，太明显了，仔细一想，确实是，一开始全是反面向上，要想达到正面向上，必须翻奇数次，也就是说，第n枚硬币要想正面向上，必须满足n的因数个数为奇数，比如说16，因数有1，16，，2，8，，4.也就是说，除了sqrt（n）外，因数都是成双成对出现的，故只有平方数的sqrt为整数。
#include<iostream>
using namespace std;
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i*i<=n;i++)printf("%d ",i*i);
putchar('\n');
}
return 0;
} H: 邱总的游戏
这题感觉很难想，确实很难想，反正我这等渣渣是想不出来的。后来群里出题人讲的：必胜状态是谁先构造出Q_ _Q并且剩余空位有偶数个时谁就必胜。因为对方若填入2个Q之间的某个空位某个字符，自己方就一定胜，对方填入其他的空格，自己再填到其他的空格，自己总能赢。
先笔推前面几种n小的，发现1<=n<=6时，一定是平局。
n=7时ksf胜，因为当n=7时，ksf把Q放中间，然后左三右三空，qz无论怎么放，ksf总能构造必胜状态。当n为>=7的奇数时ksf必胜。
当为偶数时，ksf一定不能先放Q，因为这样的话qz接着隔两位放一个Q就必胜了，因此ksf先放A，A的隔壁两个位置qz是不能放Q的，否则马上输。于是，A往两边放，连续的不与A紧邻的空格数越多，只要个数>=7，qz就必胜，因此ksf的策略是往中间放(偶数的中间两个任意一个），于是qz必胜的情况为n/2-1>=7，即n>=16.当n为8~14之间的偶数时，必为平局。
#include<iostream>
#include<algorithm>
using namespace std;
int t,n;
char *ans[3]={"Draw","ksfnb","qznb!"};
int main()
{
cin>>t;
while(t--)
{
cin>>n;
int ok;
if(n<7)ok=0;
else
{
if(n&1)ok=1;
else if(n<16)ok=0;
else ok=2;
}
cout<<ans
<<endl;
}
return 0;
} I: 二律的日常
比赛时没写出来。比赛时开始想着先排序，这个思路显然是错误的，题目要依次拿，假若礼物价格依次是12，3，4，7，需要2个礼物，若排序，拿3+4+（7-1）=13元，而实际上拿13的话会买12的，剩下1元就不够了。又想到二分，但实际上题目是不能用二分的，因为买的礼物个数并不随着拥有钱数增加而增加，比如礼物12，1，1元，我拿12元买1个，拿2元反而买2个。
正确的做法是贪心，代码实现有许多细节需要注意。如果n=k则ksf带多少钱都可以，如果礼物0元个数>k则不可能买只买k件。0元礼物很特殊，必须买，没有余地。其他正常情况的话，设有num个0元礼物，则还需从左往右买k-num个非0礼物，再取右边最低的非0元礼物价格-1加到结果上，就可以了。因为n>k,k>=num,(k-num)+num<n，因此右边一定存在这样的非0元礼物。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int t,n,k,a[100005];
int main()
{
//freopen("input.in","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
if(n==k)printf("ksfnb\n");
else
{
int num=0;
for(int i=1;i<=n;i++)if(!a[i])num++;
if(num>k)printf("alsnb\n");
else
{
long long ans=0;
int cnt=0;
int i;
for(i=1;cnt<k-num;i++)if(a[i])
{
cnt++;
ans+=a[i];
}
i--;
int minn=(1<<30);
while(++i<=n)if(a[i])minn=min(minn,a[i]);
ans+=minn-1;
printf("%lld\n",ans);
}
}
}
return 0;
}
J: 救救狗哥吧
这大水题比赛时硬是过不了。。回来理清思路很容易呀，看比赛时的代码就是写太乱了，逻辑也被乱代码搞晕了，于是就过不了，这提醒我，比赛时也不能一味求快，把代码写的很凌乱，如果水题实在过不了，不妨重新写一遍，说不定就过了，浪费不了多少时间的。还有，这题不用eps处理浮点误差也没问题，因为0.5可以被二进制精确表达，不过尽量带个eps吧。
#include<iostream>
#include<cmath>
using namespace std;
int t,a,b,c;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&a,&b,&c);
double x=-1.0*b/a/2;
int x1=floor(x),x2=ceil(x);
if(fabs(fabs(x-x1)-fabs(x-x2))<0.0000001)x1=x1;
else if(fabs(x-x1)>fabs(x-x2))x1=x2;
printf(a>0?"qznb!\n":"ksfnb!\n");
printf("%d %lld\n",x1,a*x1*x1+b*x1+(long long)c);
}
return 0;
}
K: 驯养人
生成斐波那契数列，记录一个斐波那契数是第几个斐波那契数，然后暴力搜索。
#include<cstdio>
#include<cctype>
#include<vector>
#include<iostream>
using namespace std;
int t,n;
int ok[200005],f[200005],to[200005];
vector<int> v;
bool dfs(int n)
{
if(ok[n])
{
v.push_back(n);
return 1;
}
else
{
for(int i=n-1;i>=1;i--)if(ok[i])
{
if(dfs(n-i))
{
v.push_back(i);
return 1;
}
}
}
return 0;
}
int main()
{
scanf("%d",&n);
f[0]=f[1]=1;
ok[1]=1;to[1]=1;
for(int i=2;;i++)
{
f[i]=f[i-1]+f[i-2];
if(f[i]>=200000)break;
ok[f[i]]=1;to[f[i]]=i;
}
dfs(n);
int s=v.size();
printf("xufu1e\n%d",to[v[s-1]]);
for(int i=s-2;i>=0;i--)printf(" %d",to[v[i]]);
putchar('\n');
return 0;
}
京公网安备 11010502036488号