A
你有两个变量 a 和 b 。请考虑以下对这两个变量执行的操作序列：
- 如果是 a = 0 或 b = 0 ，则结束进程。否则，转到步骤 2 ；
- 如果是 a ≥ 2·b ，则将 a 的值设置为 a - 2·b ，并重复步骤 1 。否则，转到步骤 3 ；
- 如果 b ≥ 2·a ，则将 b 的值设置为 b - 2·a ，并重复步骤 1 。
最初， a 和 b 的值都是正整数，因此过程是有限的。
您必须在进程结束后确定 a 和 b 的值。
输入
输入的唯一一行包含两个整数 n 和 m ( 1 ≤ n, m ≤ 1018 )。 n 是变量 a 的初始值， m 是变量 b 的初始值。
输出
在流程结束后打印两个整数，即 a 和 b 的值。
void solve() {
int n,m; cin >> n >> m;
while(n && m) {
if(n >= 2 * m) {
int t = n / (m * 2);
n -= t * 2 * m;
}
else if(m >= 2 * n) {
int t = m / (n * 2);
m -= t * 2 * n;
}
else break;
}
cout << n << ' ' << m << endl;
}
很简单,只有每次减的时候要尽可能的多减这点没写会t,其他的按题意实现.
B
波利卡普为准备编程比赛制定了自己的训练计划。他将训练 n 天，所有天数从 1 到 n ，从第一天开始。
在 i 这一天，波利卡普必须解决ai个问题。一天晚上，波利卡普计划庆祝赤道。他将在这样一天的第一个晚上庆祝赤道，从训练开始到今天，他将解决一半或更多的问题。
确定波利卡普庆祝赤道日的日期。
输入
第一行包含一个整数 n ( 1≤n≤200000) – 准备编程竞赛的天数。
第二行包含一个序列 a1,a2,…,an ( 1≤ai≤10000 )，其中 ai等于波利卡普要在 i 这一天解决的问题数
输出
打印波利卡普庆祝赤道日的指数。
实际上，就是求第几天的时候，解决的问题是全部问题的一半及以上
···cpp
int a[N];
void solve() {
int sum = 0;
int n; cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
int t = 0,d;
if(sum & 1) {
d = sum / 2 + 1;
}
else d = sum / 2;
for(int i = 1; i <= n; i++) {
t += a[i];
if(t >= d) {
cout << i << endl;
return;
}
}
}
先求出总和sum，d是全部问题的一半及以上的那个数，易错点是如果sum是奇数，d是sum/2还要加上1
最后再遍历一边数组，当t大于等于d是输出此时的i，即为天数。
C
给你两个字符串 s 和 t ，这两个字符串都只包含小写拉丁字母。
子串 s[l..r]s[l..r] 是将字符 sl,sl+1,…,srsl,sl+1,…,sr 不改变顺序得到的字符串。
字符串 a 在字符串 b 中出现的每个位置都是 i ( 1≤i≤|b|−|a|+1 )，这样 b[i..i+|a|−1]=ab[i..i+|a|−1]=a ( |a||a| 是字符串 aa 的长度)。
我们向您提出了 q 个查询：对于 ii -th 查询，您需要计算字符串 tt 在子串 s[li..ri]s[li..ri] 中出现的次数。
输入
第一行包含三个整数 n 、 m 和 q ( 1≤n,m≤103 、 1≤q≤105 )，分别是字符串 s 的长度、字符串 t 的长度和查询次数。
第二行是仅由小写拉丁字母组成的字符串 s ( |s|=n|s|=n )。
第三行是仅由小写拉丁字母组成的字符串 t ( |t|=m|t|=m )。
接下来的 q 行分别包含两个整数 li 和 ri ( 1 ≤ li≤ ri ≤ n)– i /-查询的参数。
输出
打印 q 行 – i -th 行应包含 i -th 查询的答案，即字符串 t 在子串 s[li..ri]s[li..ri] 中出现的次数。
题意是字符串s中的一段中数有几个字符串t
我是直接用哈希查，但好像也可以直接暴力再用前缀优化一下？
int base = 131;
int has[N],p[N];
int f(int l,int r) {
return (has[r] - has[l - 1] * p[r - l + 1]);
}
void solve() {
int n,m,q;
cin >> n >> m >> q;
p[0] = 1;
for(int i = 1; i <= n; i++) {
p[i] = p[i - 1] * base;
}
string s1,s2; cin >> s1 >> s2;
s1 = " " + s1;
s2 = " " + s2;
has[0] = 0;
for(int i = 1; i <= n; i++) {
has[i] = (has[i - 1] * base + s1[i]);
}
int t = 0;
for(int i = 1; i <= m; i++) {
t = (t * base + s2[i]);
}
int l,r,ans;
while(q--) {
cin >> l >> r;
ans = 0;
for(int j = l; j + m - 1 <= r && j + m - 1 <= n; j++) {
if(f(j,j + m - 1) == t) ans++;
}
cout << ans << endl;
}
}
D
您正在玩一款新的著名格斗游戏：Kortal Mombat XII。您必须对对手的角色施暴。
您是在新一代游戏机上玩游戏，因此您的游戏手柄上有 26 个按钮。每个按钮上都写有一个从 “a “到 “z “的小写拉丁字母。按钮上的所有字母都是成对的。
你会得到一连串的攻击，其中 i 次攻击会对对方角色造成 ai 个单位的伤害。要执行 i /th击，您必须按下游戏手柄上的 si 按钮。攻击次数从 1 到 n 不等。
你知道，如果你连续按下某个按钮超过次 k ，它就会坏掉。您很爱惜您的游戏手柄，不想弄坏它的任何按钮。
要实施暴击，您必须在给定的序列中击出几下。您可以跳过其中任何一击，但禁止更改序列的初始顺序。造成的总伤害是 ai 与所有未跳过的 i 的总和。
注意，如果跳过击打，则连续按下按钮的计数器不会重置。
你的任务是跳过一些击打，尽可能对对手的角色造成大的总伤害，同时不破坏你的游戏手柄按钮。
输入
输入的第一行包含两个整数 n 和 k ( 1≤k≤n≤2⋅105)–点击次数和连续按下同一按钮的最大次数。
输入的第二行包含 n 个整数 a1,a2,…,an ( 1≤ai≤109)，其中 ai 是 i -th 命中的伤害。
输入的第三行包含由 n 个小写拉丁字母组成的字符串 s –命中序列(每个字符都是执行相应命中时需要按下的按钮上的字母)
输出
打印一个整数 dmg – 在不破坏游戏手柄按键的情况下对对方角色造成的最大伤害。
对一个按钮不能连续按k次，比如有一串‘aaaaaa’，你最多按4次，就是要从这里面找到最大的4个，只有在连续的情况下才要反悔，那假如’aaaaaa‘后面跟了’baaa’，这三个a都可以继续按，这里比较易错。然后我直接反悔贪心实现嘛，代码如下
int b[N];
void solve() {
int n,k; cin >> n >> k;
for(int i = 0; i < n; i++) cin >> b[i];
string s; cin >> s;
priority_queue<int,vector<int>,greater<int>> pq;
int ans = 0;
int cnt = 1;
for(int i = 0; i < n; i++) {
int t = s[i] - 'a';
if(i != 0 && s[i] == s[i - 1]) {
cnt++;
}
else if(i != 0 && s[i] != s[i - 1]) {
cnt = 1;
while(pq.size()) pq.pop();
}
if(cnt <= k) {
pq.push(b[i]);
ans += b[i];
}
else {
int mn = pq.top();
if(b[i] > mn) {
pq.pop();
pq.push(b[i]);
ans += b[i] - mn;
}
}
}
cout << ans << endl;
}
E
我的解法是每个单词记录它最后出现的位置，在查询时比较每个字母最后出现的位置，ans就是最大值
int cnt[N],a[26][N];
void solve() {
int n; cin >> n;
string s; cin >> s;
for(int i = 0; i < n; i++) {
int t = s[i] - 'a';
cnt[t]++;
a[t][cnt[t]] = i + 1;
}
int m; cin >> m;
while(m--) {
string ss; cin >> ss;
sort(ss.begin(),ss.end());
int ans = a[ss[0] - 'a'][1];
int c = 1;
for(int j = 1; j < sz(ss); j++) {
if(ss[j] == ss[j - 1]) c++;
else {
int t = ss[j - 1] - 'a';
ans = max(a[t][c],ans);
c = 1;
}
}
int t = ss.back() - 'a';
ans = max(a[t][c],ans);
cout << ans << endl;
}
}
F
bool check(int x,int y) {
string s1 = to_string(x),s2 = to_string(y);
int p = 0;
for(int i = 0; i < sz(s2); i++) {
if(s2[i] == s1[p]) {
p++;
}
}
return p == sz(s1);
}
void solve() {
vector<int> g;
int n; cin >> n;
for(int i = 1; i * i <= n; i++) {
g.pb(i * i);
}
int ans = -1;
for(auto i : g) {
if(check(i,n)) ans = sz(to_string(n)) - sz(to_string(i));
}
cout << ans << endl;
}
对于一个数，你删掉其中的几个数后，一定比原来小（废话），所以可以先把比n小的平方数加入g，check函数检查这个平方数是不是由n中的几个数组成，ans是删掉数的个数，越后面的ans一定越小，直接更新就行
G
最多选k首歌,所以一定是按美感从大到小选的,选的过程中,如果没满k先加进去（不一定对mx有影响）,已满的话因为此时美感最小值就是现在遍历到的b(所以t是一定进ts里的，因为最小值已经变了)，所以比较sum（总长度） * b和mx，更新mx。最后的mx就是最大值
signed main() {
int n, k;
cin >> n >> k;
vector<PII> songs(n);
for (int i = 0; i < n; ++i) {
int t, b;
cin >> t >> b;
songs[i] = {b, t};
}
sort(songs.rbegin(), songs.rend());//先按美感从大到小排
priority_queue<int, vector<int>, greater<int>> ts;
int sum = 0;
int mx = 0;
for (auto [b, t] : songs) {
ts.push(t);
sum += t;
if (ts.size() > k) {
sum -= ts.top();
ts.pop();
}
mx = max(mx, sum * b);
}
cout << mx << endl;
return 0;
}
H
这个也是看了题解才知道要用二分答案，位掩码也是第一次接触😢,先想它二分的是什么，显然是那个最小值，对于要check的最小值mid，看能否找到一组i，j使得这两个数组组成的新数组中的每个数都大于mid。如果可以l = mid + 1,否则r = mid – 1;怎么快速的check就要用到位掩码，我们对这个数组i中的每个数，如果这个数大于mid，就用位运算使对应位置上字符变为1，最后我们得到的是一个数，它的二进制就是有满足条件的1和不满足条件的0构成。然后每个数组对mid都有这么一个数，然后就看有没有两个数能 | 起来其二进制为1，即满足所有条件（每个数都大于mid），然后返回i，j，这就是check
int a[N][10];
int n,m;
PII check(int x) {
map<int,int> mp;
for(int i = 1; i <= n; i++) {
int t = 0;
for(int j = 1; j <= m; j++) {
if(a[i][j] >= x) t = t | (1 << (j - 1));
}
mp[t] = i;
}
for(auto [t1,i] : mp) {
for(auto [t2,j] : mp) {
if((t1 | t2) == (1 << m) - 1) {
return {i,j};
}
}
}
return {-1,-1};
}
void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
int l = 0,r = inf;
PII no = {-1,-1};
while(l <= r) {
int mid = l + r >> 1;
PII f = check(mid);
if(f != no) l = mid + 1;
else r = mid - 1;
}
auto [i,j] = check(r);
cout << i << ' ' << j << endl;
}
I
主要内容是先加上每条线段上有几个点，然后减去这条线段和其他线段的交点数，记得最后要加上总共的交点数
一个知识点，（x1,y1）,(x2,y2)之间的整点数为gcd(x1 – x2，y1 – y2) + 1.
int ans;
struct node {
int x,y;
}p[N];
const node fl = {(int)1e7,(int)1e7};
struct line {
node a,b;
int d;//线段内的整数点
}L[N];
// 判断 x 是否在区间 [l, r] 中
bool in(int x, int l, int r) {
if(l > r) swap(l, r);
return l <= x && x <= r;
}
set<node> s[N],glo;//每条线段与其他线段的交点，所有的交点
bool operator < (node a, node b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
node get(line a,line b) {
// 第一个线段起点和方向单位向量
int x0 = a.a.x, y0 = a.a.y;
int u0 = (a.b.x - a.a.x) / a.d;
int v0 = (a.b.y - a.a.y) / a.d;
// 第二个线段起点和方向单位向量
int x1 = b.a.x, y1 = b.a.y;
int u1 = (b.b.x - b.a.x) / b.d;
int v1 = (b.b.y - b.a.y) / b.d;
// 解方程组：使 a.a + k*u0 == b.a + k1*u1
//k1,k0是整数之间的步长
// 转化为同余形式，求 k1
int up1 = (y1 - y0) * u0 - (x1 - x0) * v0;
int dw1 = u1 * v0 - v1 * u0;
// 若 dw1 == 0 ,说明两条直线共线或者平行
//或 up1 % dw1 ≠ 0，表示 k1 不是整数，因此不会有整点交点
if(!dw1 || up1 % dw1) return fl;
int k1 = up1 / dw1;
int x = x1 + k1 * u1, y = y1 + k1 * v1;//交点
// 判断交点是否在两条线段上
if(
in(x, a.a.x, a.b.x) &&
in(y, a.a.y, a.b.y) &&
in(x, b.a.x, b.b.x) &&
in(y, b.a.y, b.b.y)
) {return { x, y };}
else {
return fl;
}
}
void solve() {
int n; cin >> n;
for(int i = 1;i <= n; i++) {
cin >> L[i].a.x >> L[i].a.y >> L[i].b.x >> L[i].b.y;
L[i].d = __gcd(abs(L[i].a.x - L[i].b.x), abs(L[i].a.y - L[i].b.y));
//从一个端点走到另一个端点的整数格点上，共跨越了多少个“最小单位步长”。
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i != j) {
node p = get(L[i], L[j]);
if(p.x != 1e7) {
s[i].insert(p);
glo.insert(p);
}
}
}
ans += L[i].d + 1 - s[i].size();
}
cout << ans + glo.size();
}
结束了，没有总结捏😫
