A 做游戏
牛牛和 牛可乐在玩石头剪刀布。
众所周知，石头剪刀布的规则是这样的：
- 在一局游戏中，双方各自出石头、剪刀、布其一。
- 胜负关系如下：
牛牛和 牛可乐进行了多轮游戏， 牛牛总共出了 A 次石头，B 次剪刀，C 次布；牛可乐总共出了 X 次石头，Y 次剪刀，Z 次布。 你需要求出 牛牛最多获胜多少局。
输入描述:
第一行，三个非负整数 A,B,C 。
第二行，三个非负整数 X,Y,Z 。
保证 A+B+C=X+Y+Z, 0<= A,B,C,X,Y,Z<= 10^9A+B+C=X+Y+Z,0≤A,B,C,X,Y,Z≤10
9
。
输出描述:
输出一行，一个整数表示答案。
示例1
输入
复制
114514 0 0
0 114514 0
输出
复制
114514
思路：要求妞妞最多胜了多少局，只需要在必赢的局数上面取min，比如min(石头,剪刀)，这就是石头最多能够赢的局数，同理min(剪刀，布),min(布，石头),因为题目保证了A+B+C=X+Y+Z，剩下来多余的剪刀石头布为使赢的局数最大总能打平局。
代码：
#include<iostream>
using namespace std;
typedef long long int ll;
int main(){
ll A,B,C,X,Y,Z;
cin>>A>>B>>C>>X>>Y>>Z;
ll ans=min(A,Y)+min(B,Z)+min(C,X);
cout<<ans<<endl;
}
G 判正误
思路：题目简单易懂只需要判 a ^ d + b ^ e + c ^ f == g 就行了，不过math.h提供的pow时间复杂度O(n)用快速幂可以达到O(log)，因为10910^9 可能暴long long 了，所以玄学mod 1e9 + 7
代码：
#include<iostream>
using namespace std;
const int mod = 1e9 + 7;
typedef long long int ll;
ll a,b,c,d,e,f,g;
ll _pow(ll a,ll n){
ll ans=1;
while(n){
if(n&1)ans=(ans*a)%mod;
a=(a*a)%mod;
n>>=1;;
}
return ans;
}
int main(){
int T;cin>>T;
while(T--){
cin>>a>>b>>c>>d>>e>>f>>g;
ll x=_pow(a,d);
ll y=_pow(b,e);
ll z=_pow(c,f);
if(g == x+y+z){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
}
B 排数字
思路：先注意到 61616是可以组成两个的，中间的重复用了一次，因为可以任意排，所以只需要统计6的个数和1的个数，然后分类处理。当6的个数>1的个数 ，答案是1的个数，当6的个数等于1的个数答案是1的个数-1，当6的个数<1的个数答案是6的个数-1
代码：
#include<iostream>
#include<string>
using namespace std;
int six,one;
int main(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++){
char x;scanf(" %c",&x);
if(x=='6')six++;
if(x=='1')one++;
}
if(six>one)
cout<<one<<endl;
else if(six==one)
cout<<one-1<<endl;
else cout<<six-1<<endl;
}
D 数三角
思路：O(n^3)枚举每个三角形，求出每个三角形的三条边，满足最大边的平方>较小边的平方和一定是钝角，并且需要把共线的平角特殊判掉。
代码：
#include<iostream>
#include<math.h>
using namespace std;
const int maxn = 1e3+10;
struct point{
int x,y;
point(){}
point(int a,int b):x(a),y(b){}
}ans[maxn];
long long distance(int x1,int y1,int x2,int y2){
return (long long)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main(){
int n;cin>>n;
int res=0;
for(int i=0;i<n;i++)scanf("%d%d",&ans[i].x,&ans[i].y);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
for(int k=j+1;k<n;k++){
long long a=distance(ans[i].x,ans[i].y,ans[j].x,ans[j].y);
long long b=distance(ans[j].x,ans[j].y,ans[k].x,ans[k].y);
long long c=distance(ans[i].x,ans[i].y,ans[k].x,ans[k].y);
bool flag = ((ans[k].y-ans[i].y)*(ans[j].x-ans[i].x)-(ans[j].y-ans[i].y)*(ans[k].x-ans[i].x))==0;
long long m=max(a,max(b,c));
if(m == a&&b + c < a&&!flag)res++;
if(m == b&&a + c < b&&!flag)res++;
if(m == c&&a + b < c&&!flag)res++;
}
}
}
cout<<res<<endl;
}
F 拿物品
思路：为了使得H和T属性和越大，每次选择最大的属性总是好的，当牛牛选择ai属性，意味着可乐牛将损失bi属性，换言之就是牛牛得到ai+bi属性，为使得属性和最大，需要一次降序排序，在依次选取即可。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5*2 + 10;
struct node{
long long int v;
int ind;
}a[maxn];
bool cmp(node a,node b){
return a.v>b.v;
}
int main(){
int n;cin>>n;
for(int i=0;i<n;i++)cin>>a[i].v;
for(int i=0;i<n;i++){
long long int x;cin>>x;
a[i].v+=x;
a[i].ind=i;
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
if(!(i&1))cout<<1+a[i].ind<<" ";
}
cout<<endl;
for(int i=0;i<n;i++){
if(i&1)cout<<1+a[i].ind<<" ";
}
}
E 做计数
思路：
根号i + 根号j = 根号k (两边同时平方)
i + j +根号 i * j = k
因为k是一个整数，所以等式存在的冲要条件是 i *j 是完全平方数
有i *j <=n，所以我们只需要枚举[1,n]的完全平方数，并且求出他们的因子个数就是答案了。
代码：
#include<iostream>
using namespace std;
typedef long long int ll;
ll n;
int main(){
cin>>n;
int ans=0;
for(int i=1;i*i<=n;i++){
for(int j=1;j<=i;j++){
if((i*i)%j==0)ans+=2;
if(j*j == i*i)ans-=1;
}
}
cout<<ans<<endl;
}
C 算概率
思路：
dp[i][j]:表示前i道题正确j道题目的概率
转移方程：dp[i][j] = dp[i-1][j]*(1-p[i])+p[i]*dp[i-1][j-1]
动态规划太过巧妙。
代码：
#include<iostream>
using namespace std;
typedef long long int ll;
const int mod = 1e9 + 7;
const int maxn = 1e3*2 + 10;
ll dp[maxn][maxn],p[maxn];
/* dp[i][j]:表示前i道题正确j道题目的概率 转移方程：dp[i][j] = dp[i-1][j]*(1-p[i])+p[i]*dp[i-1][j-1] */
int main(){
ll n;cin>>n;
dp[0][0]=1;
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=1;i<=n;i++){
dp[i][0] = dp[i-1][0]*(mod+1-p[i])%mod;
for(int j=1;j<=i;j++){
dp[i][j] = (dp[i-1][j]*(mod+1-p[i]) + (p[i])*(dp[i-1][j-1]))%mod;
}
}
for(int i=0;i<=n;i++)
cout<<dp[n][i]<<" ";
}
京公网安备 11010502036488号