A
签到
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n;
map<int, char> m;
int a[N];
char s[N];
int main() {
int t;
cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], m[a[i]] = '0';
scanf("%s", s + 1);
// m.clear();
bool f = 1;
set<char> ss[55];
for(int i = 1; i <= n; i++) {
ss[a[i]].insert(s[i]);
if(ss[a[i]].size() > 1) {
f = 0;
break;
}
}
if(f) puts("YES");
else puts("NO");
}
system("pause");
return 0;
}
B
模拟即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, q;
int a[N];
int op, x;
int main() {
int t;
cin >> t;
while(t--) {
cin >> n >> q;
int even = 0, odd = 0;
ll s = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if(a[i] % 2) odd += 1;
else even += 1;
s += a[i];
}
int change = 0;
while(q--) {
scanf("%d%d", &op, &x);
if(op == 0) {
s += 1ll * x * even;
printf("%lld\n", s);
if(x % 2 == 1) {
even = 0;
odd = n;
}
}
else {
s += 1ll * x * odd;
printf("%lld\n", s);
if(x % 2 == 1) {
even = n;
odd = 0;
}
}
}
}
system("pause");
return 0;
}
C
模拟。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5 + 10;
int n, q;
char s[N], now_c;
int ti[N];
int main() {
int t;
cin >> t;
while(t--) {
cin >> n; getchar(); scanf("%c", &now_c);
scanf("%s", s + 1);
for(int i = n + 1; i <= 2 * n; i++) s[i] = s[i - n];
for(int i = 1; i <= 2 * n; i++) ti[i] = 1e9;
int ans = 0;
int mn_g = 1e9;
for(int i = 2 * n; i >= 1; i--) {
if(s[i] == 'g') {
mn_g = i;
ti[i] = 0;
}
else {
if(mn_g == 1e9) continue;
ti[i] = mn_g - i;
}
if(s[i] == now_c) ans = max(ans, ti[i]);
}
printf("%d\n", ans);
}
system("pause");
return 0;
}
D
贪心。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, q;
int a[N];
int cnt[42];
map<ll, int> f;
int main() {
ll w = 1;
int c = 0;
while(w <= 1e9) {
w *= 2;
c++;
f[w] = c;
}
int t;
cin >> t;
while(t--) {
cin >> n;
int tot = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
tot += f[(a[i] & (-a[i]))];
}
int more = n - tot;
if(more <= 0) {
puts("0");
continue;
}
for(int i = 0; i <= 30; i++) cnt[i] = 0;
ll mx = 0; // 下标最多可以组成 2^mx
for(int i = 2; i <= n; i += 2) {
int k = (i & (-i));
k = f[k];
cnt[k] += 1;
mx += k;
}
if(mx < more) puts("-1");
else {
int ans = 0;
for(int i = 30; i >= 1; i--) {
while(cnt[i] > 0 && more > 0) {
more -= i;
cnt[i]--;
ans++;
}
if(more <= 0) break;
}
printf("%d\n", ans);
}
}
system("pause");
return 0;
}
E1
直接当E2做的，wa了很多发。
枚举即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, q;
ll a, b, c, d;
bool inline check(ll x, ll y) {
return (x > a && x <= c && y > b && y <= d);
}
int main() {
int t; cin >> t;
while(t--) {
cin >> a >> b >> c >> d;
bool f = 0;
for(ll i = a + 1; i <= c; i++) {
ll k = __gcd(a * b, i);
k = (a * b) / k;
ll k2 = d / k;
if(k * k2 > b && k * k2 <= d) {
f = 1;
cout << i << ' ' << k2 * k << endl;
break;
}
}
if(f) continue;
puts("-1 -1");
}
system("pause");
return 0;
}
E2
分析可知，新得到的x和y必然包含a*b的所有因子，那么就按这个思路分即可。
怎么分？有OEIS可知一个1e9大小的数大约有1300+种不同的因子，枚举这些因子。
因为这两部分因子不一定位于给定区间范围内，再乘上系数放大一下即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, q;
ll a, b, c, d;
bool inline check(ll x, ll y) {
return (x > a && x <= c && y > b && y <= d && x * y % (a * b) == 0);
}
int main() {
int t; cin >> t;
while(t--) {
cin >> a >> b >> c >> d;
bool f = 0;
vector<int> va, vb;
for(int i = 1; 1ll * i * i <= a; i++) {
if(a % i == 0) {
va.push_back(i);
if(1ll * i * i != a) va.push_back(a / i);
}
}
for(int i = 1; 1ll * i * i <= b; i++) {
if(b % i == 0) {
vb.push_back(i);
if(1ll * i * i != b) vb.push_back(b / i);
}
}
for(auto i : va) {
if(f) break;
for(auto j : vb) {
ll x = 1ll * i * j, y = 1ll * a * b / i / j;
x *= (a / x + 1);
y *= (b / y + 1);
if(x <= c && y <= d) {
f = 1;
cout << x << ' ' << y << endl;
break;
}
}
}
if(!f) puts("-1 -1");
}
system("pause");
return 0;
}
F
思路就是按照mex递增的方式计算贡献。（先分析）
需要注意细节，细节见代码。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, q;
int a[N], pos[N];
signed main() {
int t; cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
pos[a[i]] = i;
}
int L = pos[0], R = pos[0];
int lcnt = L - 1, rcnt = n - R;
int ans = 1;
for(int len = 2; len <= n; len++) {
if(len % 2) {
L = min(L, pos[len / 2]);
R = max(R, pos[len / 2]);
lcnt = L - 1;
rcnt = n - R;
}
int more = len - (R - L + 1);
if(more < 0) continue;
// 左边选 x 个，右边选 more - x 个
int mx = min(lcnt, more), mn = more - rcnt;
if(mx >= mn) ans += (mx - max(0ll, mn) + 1);
// cout <<"mx:" << mx << " mn:" << mn << " add:" << (mx - max(0, mn) + 1) << " ans:" << ans<< endl;
}
printf("%lld\n", ans);
}
system("pause");
return 0;
}
p.s.
第一次做出了div3所有题目！绿了耶( •̀ ω •́ )y