A
逆序输出两个字符串
#include <bits/stdc++.h>
using namespace std;
int main() {
string a,b;
cin >> a >> b;
cout << b << a;
return 0;
}
B
先用掉 a ,再用掉 b,输出剩余部分
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
LL a, b,c;
cin >> a >> b >> c;
if(a < c) c -= a,a = 0;
else a -= c,c = 0;
if(b < c) c -= b,b = 0;
else b -= c,c = 0;
cout << a <<' ' << b;
return 0;
}
C
找到大于 或 等于 (x) 的最小质数
线性筛 + 二分
直接暴力也能过。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 100;
bool st[N];
int k,pri[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(int i = 2;i <= N; ++i) {// 线性筛
if(!st[i]) pri[k ++] = i;
for(int j = 0;pri[j] <= N / i; ++j) {
st[pri[j] * i] = 1;
if(i % pri[j] == 0) break;
}
}
int x;
cin >> x;
int l = 0,r = k;
while(l < r) {// 二分
int mid = l + r>> 1;
if(pri[mid] >= x) r = mid;
else l = mid + 1;
}
cout << pri[l];
return 0;
}
D
题目大意
你和机器人玩剪刀石头布,机器人输入一个长度为(N) 的序列,(r)代表石头,(s) 代表剪刀,(p)代表布
每(K) 次为一个回合,第一个回合你可以出任何手势,从第二个回合开始你出的手势不能和上一个回合相同
即(hand[i] != hand[i - k]) ,每次获胜,分别赢 (r,s,p) 个分数,平局不计分,问你最大的获胜分数
思路
观察题目发现,从第二轮开始,你每次出的手势,都要考虑上一轮出过的,不能重复。
那么,我们首先考虑,赢下当前这局所需要的手势,是不是上轮出过的,如果出过,就和机器人相同的手势保证平局,否则就出必胜手势。
我们用(vis) 数组来保存,当前第(i) 位是否出过必胜手势
用 (t) 数组来保存机器人出的手势序列
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char t[N];
bool vis[N];
int r,s,p,n,k,ans = 0;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> k >> r >> s >> p ;
for(int i = 1;i <= n; ++i) {
cin >> t[i];
if(i - k > 0 && vis[i - k] && t[i] == t[i - k]) continue;
// 如果当前不是第一轮,并且vis[i-k]出过必胜手势,并且t[i]==t[i-k],说明我们只能平局
if(t[i] == 'r') ans += p;
if(t[i] == 's') ans += r;
if(t[i] == 'p') ans += s;
vis[i] = 1;// 当前局势出过必胜手势
}
cout << ans;
return 0;
}
E
前缀和 + 二分答案
题意
有(n) 个人,每个人的能力值是(A_i) ,要进行(M)次握手,每次握手可以选择左手握的值(L),右手握的值(R)
每次握手得到的幸福值为(L+R),问进行(M)次操作后,得到的最大幸福值
其中 ((L,R) eq (R,L))
思路
首先二分单次操作中所获得的最小幸福值,记作(mid) ,然后计算,以此值作为幸福值的边界,
可以握多少次手,如果握手次数大于(M)则扩大这个(mid) ,否则缩小。
对于每次二分得到的(mid) ,针对每一个(a[i])计算另一个值(mid-a[i])的下标(pos)。
所以目前就获得了 (n-pos+1) 对握手,然后把这些握手得到的幸福值加到(res) 中
(sum) 是前缀和数组,(sum[n]-sum[pos-1]) 得到 (n-pos) 这些值的和再加上(n-pos+1)个(a[i])
因为(cnt) 最后不一定刚等于(m) ,(cnt) 只是第一次二分的(check) 函数 ,有可能大于 (m)
所以最后在减去多余的即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define endl '
'
typedef long long LL;
LL sum[N],a[N],m,n;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n; ++i) cin >> a[i];
sort(a+1,a+1+n);
for(int i = 1;i <= n; ++i) sum[i] = sum[i - 1] + a[i];
LL l = 0,r = 2*N,ans,res,cnt;
while(l < r) {
LL mid = l + r + 1 >> 1;
res = cnt = 0;
for(int i = 1;i <= n; ++i) {
LL pos = lower_bound(a+1,a+1+n,mid-a[i]) - a;
cnt += n - pos + 1;
res += sum[n] - sum[pos - 1] + a[i] * (n - pos + 1);
}
if(cnt >= m) l = mid;
else r = mid - 1;
}
cout << res - (cnt - m) * l << endl;
}