A
solution:
直接输出min(石头，剪刀) + min(剪刀，布) + min(布，石头)呗
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll a,b,c,d,e,f;
cin>>a>>b>>c;
cin>>d>>e>>f;
cout<<min(a , e) + min(b , f) + min(c , d)<<endl;
return 0;
}B
solution:
记录6和1的个数，最后输出min(1的个数，6的个数-1)即可
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int n,cnt1 = 0,cnt6 = 0;
string s;
cin>>n>>s;
for(int i=0;i<n;i++){
if(s[i] == '6') cnt6++;
if(s[i] == '1') cnt1++;
}
cout<<min(cnt1 , cnt6 - 1)<<endl;
return 0;
}C
solution:
设dp[i][j]代表前i道题做对了j道的概率，a[i]是第i道题做对概率，通项公式就是：
dp[i][j] = dp[i-1][j]×(mod - a[i] + 1) + dp[i-1][j-1]×a[i]
这大概是我仅能做出来的概率dp题了
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2002;
const ll mod = 1e9+7;
ll a[maxn];
ll dp[maxn][maxn];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
dp[0][0] = 1;
for(int i=1;i<=n;i++){
dp[i][0] = dp[i-1][0]*(mod - a[i] + 1);
dp[i][0] %= mod;
for(int j=1;j<=i;j++){
dp[i][j] = dp[i-1][j]*(mod - a[i] + 1) + dp[i-1][j-1]*a[i];
dp[i][j] %= mod;
}
}
for(int i=0;i<=n;i++){
if(i != 0)
printf(" ");
printf("%lld",dp[n][i]);
}
return 0;
}
D
solution:
三层for循环，记得特判三个点共线！
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 502;
double a[maxn],b[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
int ans = 0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
for(int k=j+1;k<=n;k++){
int x = i, y = j ,z = k;
double k1 = (a[x] - a[y])*(a[x] - a[y]) + (b[x] - b[y])*(b[x] - b[y]);
double k2 = (a[x] - a[z])*(a[x] - a[z]) + (b[x] - b[z])*(b[x] - b[z]);
double k3 = (a[y] - a[z])*(a[y] - a[z]) + (b[y] - b[z])*(b[y] - b[z]);
double maxx = max(k1 ,max(k2 ,k3));
if(sqrt(k1) + sqrt(k2) + sqrt(k3) - sqrt(maxx) > sqrt(maxx) && k1 + k2 + k3 - maxx < maxx){
ans++;
}
}
}
}
printf("%d\n",ans);
return 0;
}E
solution:
两边平方一下就是i + j + 根号下(i*j) = k
题目要求i，j，k都是整数，所以i*j一定是一个平方数
所以我们只需要枚举根号下n的每一个数，求其平方数的所有因子
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int n,ans = 0;
scanf("%d",&n);
for(int i=1;i<=sqrt(n);i++)
{
int x = i*i;
for(int j=1;j<=sqrt(x);j++){
if(x%j == 0){
int y = x/j;
int z = j;
if(y != z){
ans+=2;
}else{
ans+=1;
}
}
}
}
cout<<ans<<endl;
return 0;
}F
solution:
题目说明牛牛和牛可乐都希望自己的得分尽量比对方大(最大化自己与对方得分的差)
牛牛实际得分 = 牛牛选择的物品和ai - 牛可乐选择的物品bi
牛可乐实际得分 = 牛可乐选择的物品和bi - 牛牛选择的物品和ai
计sum(a+b) 等于n个物品的ai+bi，将sum(a+b)分别加到他们的实际得分
牛牛得分 = sum(a) + 牛牛选择的物品ai + 牛牛选择的物品bi
牛可乐得分 = sum(b) + 牛可乐选择的物品bi + 牛可乐选择的物品ai
sum(a)和sum(b)都是定值，所以只需要将ai+bi从大到小排序，每个人依次取即可
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
ll a[maxn],b[maxn];
struct node{
ll x;
int i;
friend bool operator<(node p1,node p2){
return p1.x<p2.x;
}//优先队列最da值优先
};
priority_queue<node> q;//优先较大队列
vector<int> v1,v2;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
node now ;
now.x = 1ll*(a[i] + b[i]);
now.i = i;
q.push(now);
}
int flag = 0;
while(!q.empty())
{
node now = q.top();
q.pop();
if(flag == 0){
flag = 1;
v1.push_back(now.i);
}
else{
flag = 0;
v2.push_back(now.i);
}
}
for(int i=0;i<v1.size();i++){
if(i != 0)
printf(" ");
printf("%d",v1[i]);
}
printf("\n");
for(int i=0;i<v2.size();i++){
if(i != 0)
printf(" ");
printf("%d",v2[i]);
}
return 0;
}G
solution:
这是一道hash题~，取不同的mod执行快速幂，如果都相同说明猜想成立
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod1 = 1e9+7;
const ll mod2 = 1e9+9;
ll mod;
ll pow_mod(ll a,ll b)
{
ll ans = 1;
while(b){
if(b&1)
ans = ans*a%mod;
a = a*a%mod;
b>>=1;
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll a,b,c,d,e,f,g;
int cnt = 0;
cin>>a>>b>>c>>d>>e>>f>>g;
mod = mod1;
if(pow_mod(a,d) + pow_mod(b,e) + pow_mod(c,f) == g) cnt++;
mod = mod2;
if(pow_mod(a,d) + pow_mod(b,e) + pow_mod(c,f) == g) cnt++;
if(cnt == 2){
printf("Yes\n");
continue ;
}
printf("No\n");
}
return 0;
}H
solution:
DP 为什么这么简单的dp我又没想明白呢，菜
先将元素按能量值排序，可证明存在一个最优方案，满足每个魔法消耗一段连续的元素。
因为要求至少取 k 段，那么只能从 k+1 开始DP
定义dp[i]代表：前i项最优解，那么可以得到转移方程：
1.是前面的，从长度m变成m+1；
2.断开前面，从当前位置往前 k−1 项，和当前第 i 项，组成长度为 k 的序列。
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 300005;
ll a[maxn],dp[maxn];
int main()
{
int n , k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+1+n);
for(int i=1;i<k;i++)
dp[i] = 1e10;
ll pre = dp[0] - a[1];
for(int i=k;i<=n;i++){
dp[i] = pre + a[i];
pre = min(pre , dp[i-k+1] - a[i-k+2]);
}
printf("%lld\n",dp[n]);
return 0;
}
I
solution:
这一题我因为没有乘个数wa了。。。。赛后过题，菜
考虑二进制贪心，二进制的异或，如果对于n个数，考虑每个数的二进制，从最低位往高位枚举，如果这n个数的第i位二进制存在既有1又有0，那么我们就将所有的第i位是0的和第i位是1的相连就行，这样保证答案最小
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
ll a[maxn];
int b[maxn][40];
map<ll ,int> mp;
int main()
{
int n,cnt = 0;
ll x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
if(mp[x] == 1){
continue ;
}
mp[x] = 1;
a[++cnt] = x;
}
if(cnt == 1){
cout<<"0"<<endl;
return 0;
}
for(int i=1;i<=cnt;i++)
{
ll x = a[i];
int z = 0;
while(x)
{
int y = x%2;
x /= 2;
b[i][++z] = y;
}
}
ll ans;
set<int> s;
for(int i=1;i<=33;i++)
{
s.clear();
for(int j=1;j<=cnt;j++)
{
int x = b[j][i];
s.insert(x);
}
if(s.size() >= 2){
ans = 1ll*(1<<(i-1));
break ;
}
}
cout<<ans*1ll*(cnt - 1)<<endl;
return 0;
}
京公网安备 11010502036488号