A
- 记录一个
flag变量，遇到(就变成 ，遇到)就变回 。然后只在 的时候输出变量。
#include <bits/stdc++.h>
using namespace std;
int main() {
string p;
cin >> p;
int n = p.size();
bool f = 0;
for (int i = 0; i < n; ++ i) {
if (p[i] == '(')\
f = 1;
if (p[i] == ')') {
f = 0;
cout << '@';
continue;
}
if (f)
continue;
cout << p[i];
}
return 0;
}
B
观察数据范围发现，我们不能暴力去统计每个区间的和（这是的）。
题目保证了为升序，所以我们可以使用二分来找到区间的左右端点：第一个大于等于的数和第一个大于的数往左一个。
然后还要快速的求出区间和，我们可以使用前缀和来的回答。
这样整体复杂度为。
#include <bits/stdc++.h>
using namespace std;
long long n, m, x[200005], c[200005], l[200005], r[200005], s[600005];
vector<long long> a;
long long find(long long f) {
long long l = 0, r = a.size() - 1;
while (l < r) {
long long mid = (l + r) / 2 + 1;
if (a[mid] <= f)
l = mid;
else
r = mid - 1;
}
return l + 1;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x[i];
a.push_back(x[i]);
}
for (int i = 1; i <= n; i++) cin >> c[i];
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> l[i] >> r[i];
a.push_back(l[i]);
a.push_back(r[i]);
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
for (int i = 1; i <= n; i++) s[find(x[i])] += c[i];
for (int i = 1; i <= a.size(); i++) s[i] += s[i - 1];
for (int i = 1; i <= m; i++) cout << s[find(r[i])] - s[find(l[i]) - 1] << '\n';
return 0;
}
C
根据题目的约束条件，钥匙的数量最多为 。测试次数也不多：。此外，如题目描述，有 种钥匙真假组合。
我们可以对所有 种组合进行 次测试，统计满足条件的组合数量。在这里，需要进行 次测试。即使每次测试进行 次操作，总操作次数也限制在 以内，这足够快，可以通过这个问题。
为了暴力枚举 种组合，我们使用按位枚举的方法。
例如，使用一个 for 循环遍历 。如果 的第 位是 ，我们认为第 把钥匙是假的；如果是 ，我们认为它是真的。通过这种方式，我们可以穷举所有的组合。
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 20;
const int SIZE_M = 1e2 + 5;
int n, m, k;
int bit[SIZE], c[SIZE_M], A[SIZE_M][SIZE_M], r[SIZE_M];
int main() {
int tot = 0;
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= m; ++ i) {
scanf("%d", &c[i]);
for (int j = 1; j <= c[i]; ++ j)
scanf("%d", &A[i][j]);
char ch;
cin >> ch;
r[i] = ch == 'x' ? 0 : 1;
tot += r[i];
}
int ans = 0;
for (int status = 0; status < (1 << n); ++ status) {
for (int i = 0; i < n; ++ i)
bit[i] = (status >> i) & 1;
int flag = 1;
for (int i = 1; i <= m; ++ i) {
int cnt = 0;
for (int j = 1; j <= c[i]; ++ j) {
if (bit[A[i][j] - 1])
++ cnt;
}
if ((cnt >= k && !r[i]) || (cnt < k && r[i])) {
flag = 0;
break;
}
}
if (flag) {
++ ans;
}
}
printf("%d\n", ans);
return 0;
}
D
- 数据量都较小，各种做法均可轻松通过。以下做法采用结构体数组排序来解题。
- 统计每一种字母出现的次数，然后将字母和次数，两个键值打包为结构体，然后按照次数为第一关键字，字母顺序为第二关键字，进行排序，最后从前到后输出即可。
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 3e2 + 5;
char s[SIZE]; //字符数组
int cnt[SIZE]; //出现频率
int main() {
cin.getline(s,256);
for (int i = 0; s[i] != '\0'; ++ i) {
char c = s[i];
if ('A' <= c && c <= 'Z') ++ cnt[c];
else if ('a' <= c && c <= 'z') ++ cnt[c-32]; //小写字母
}
for (int k = 250; k > 0; -- k) { //频率从高到低查找
for (char c = 'A'; c <= 'Z'; ++ c) {
if (cnt[c] == k)
printf("%c %d\n", c, k);
}
}
return 0;
}
E
考虑把操作倒过来，就变成每次加一个点。用并查集维护连通块以及其权值和即可。
注意开 long long，否则只会获得 50 分。
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef vector < int > vec;
const int SIZE = 4e5 + 5;
int n, m;
int a[SIZE], fa[SIZE], cnt[SIZE], vis[SIZE], ans[SIZE], del[SIZE];
vec edge[SIZE];
namespace GTR {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
int read() {
int a = 0, b = 1, c = fetch();
while (c < 48 || c > 57) b ^= c == '-', c = fetch();
while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
return b ? a : -a;
}
} using GTR::read;
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
signed main() {
// freopen("qd.in", "r", stdin);
// freopen("qd.out", "w", stdout);
n = read(), m = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1; i <= n; ++ i) fa[i] = i, cnt[i] = a[i];
for (int i = 1, u, v; i <= m; ++ i) {
u = read(), v = read();
edge[u].emplace_back(v), edge[v].emplace_back(u);
}
for (int i = 1; i <= n; ++ i) vis[i] = read();
int res = 0;
for (int i = 1; i <= n; ++ i) {
int u = vis[n - i + 1];
for (int it: edge[u]) {
int fx = find(u), fy = find(it);
if (fx == fy || !del[it]) continue;
cnt[fx] += cnt[fy], fa[fy] = fx;
res = std::max(res, cnt[fx]);
}
res = std::max(res, cnt[find(u)]);
del[u] = 1, ans[i] = res;
}
for (int i = n - 1; i; -- i) {
printf("%lld\n", ans[i]);
}
return puts("0"), 0;
}
F
测试点 1~4 5~8
直接暴力枚举 ，然后判断 。
复杂度 。
测试点 9~10
直接输出 。
测试点 11~12
对于 是奇数的情况， 一定是奇数，而 是偶数则 一定是偶数。
所以当 是奇数时， 可以是任意一个 的奇数， 是偶数时， 可以是任意一个 的偶数。
测试点 11~12
对于 是奇数的情况， 一定是奇数，而 是偶数则 一定是偶数。
所以当 是奇数时， 可以是任意一个 的奇数， 是偶数时， 可以是任意一个 的偶数。
测试点 13~15
可以依次考虑每一个 是多少，然后记 为 的这样的 的个数。
那么如果不考虑 ，答案就是 。
如何处理 ，那么我们可以把 的情况再算一次之后，把整个答案 除以 。
如何计算 的个数？实际上只有当 或 才可以，那么方案数就是 。
测试点 16~18 19~20
发现难点在于得到 ，其实对于所有 相同的 ，其 的值也相同。
而满足 的 的个数是好处理的。
所以就可以 的时间复杂度内解决此题。
#include<bits/stdc++.h>
#define ll long long
#define db double
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
int read(){
int sum=0,f=1;char st=getchar();
while(st<'0'||st>'9'){
if(st=='-')f=-1;
st=getchar();
}
while('0'<=st&&st<='9'){
sum=(sum<<3)+(sum<<1)+st-'0';
st=getchar();
}
return sum*f;
}
const int maxn=1000010;
ll cnt[maxn];
int n,m;
int main(){
cin>>n>>m;
int st=n%m;
for(ll i=1;i<=m;++i)cnt[i*i%m]+=n/m+(i<=st);
ll ans=cnt[0]*cnt[0]+cnt[0];
for(int i=1;i<m;++i)ans+=cnt[i]*cnt[m-i];
// for(int i=0;i<=m;++i)
// cout<<"i="<<i<<" cnt[i]="<<cnt[i]<<endl;
if(m%2==0)ans+=cnt[m/2];
cout<<ans/2<<endl;
return 0;
}
G
假如 ，情况很少，对于某一天你可能有这几种情况：
- 对于
001，111等情况，小C 可以翘 节课，少在教学楼呆 小时。 - 而对于
101的情况，小C 第一次可以选择翘 节课，少在教学楼呆 小时。
贪心的先选择少呆 小时的情况，剩下的只能选少呆 节课的情况。
扩展上一个做法。
对于每一天，小 C 可以选择翘 节课，少呆 个小时。
同样贪心的选择少呆时间长的课，最后如果还能翘课，那么都只能少呆 个小时。
进一步扩展上面的做法。
对于一天，我们可以考虑每一节课选择翘或者不翘，暴力得到 ，表示第 填翘 节课的情况下小 C 要在教学楼里呆最少 个小时。
然后就是一个分组背包。
时间复杂度为 。
再进一步
我们不用暴力的考虑每一节课选择翘或者不翘，而只需要考虑这一天中最早的课和最晚的课是什么就可以（中间的课翘了也不会减少呆在教学楼的时间）
所以就可以枚举最早的课 ，最晚的课 ，计算一个要翘多少课，此时小 C 要在教学楼呆 小时。
这样就可以 的时间复杂度求出 。
#include<bits/stdc++.h>
#define ll long long
#define db double
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
int read(){
int sum=0,f=1;char st=getchar();
while(st<'0'||st>'9'){
if(st=='-')f=-1;
st=getchar();
}
while('0'<=st&&st<='9'){
sum=(sum<<3)+(sum<<1)+st-'0';
st=getchar();
}
return sum*f;
}
const int maxn=510;
int n,m,q;
int a[maxn][maxn];
int b[maxn][maxn],f[maxn];
int main(){
cin>>n>>m>>q;
memset(b,0x3f,sizeof(b));
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i){
int su=0;
for(int j=1;j<=m;++j){
a[i][j]=read();
su+=a[i][j];
}
b[i][su]=0;
for(int j=1;j<=m;++j){
int st=0;
for(int k=j;k<=m;++k){
st+=a[i][k];
b[i][su-st]=min(b[i][su-st],k-j+1);
}
}
}
f[0]=0;
for(int i=1;i<=n;++i)
for(int j=q;j>=0;--j){
f[j]=f[j]+b[i][0];
for(int k=j-1;k>=0;--k)
f[j]=min(f[j],f[k]+b[i][j-k]);
}
int ans=1e9;
for(int i=0;i<=q;++i)
ans=min(ans,f[i]);
cout<<ans<<endl;
return 0;
}
H
给出每个前缀的最小循环节长度相当于给出了 数组。
相当于要实现一个“逆kmp”过程，可以类比kmp，从前往后增量地构造原串。
如果 ，那么显然 。
否则没有可以依赖的取值，但可以发现存在一些 的限制，其中的 是在从 开始一路向前跳 的过程中得到的（也就是kmp代码实现中的那个 ）。
复杂度。
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 1e5+5;
int n,nxt[N],a[N],vis[26];
int main(){
n=gi();
for (int i=1;i<=n;++i) nxt[i]=i-gi();
for (int i=2,j;i<=n;++i){
j=nxt[i-1];
while (j&&j+1!=nxt[i]) vis[a[j+1]]=i,j=nxt[j];
if (j+1==nxt[i]) a[i]=a[j+1];
else{
vis[a[1]]=i;
for (int k=0;k<26;++k) if (vis[k]!=i) {a[i]=k;break;}
}
}
for (int i=1;i<=n;++i) putchar(a[i]+'a');
puts("");return 0;
}