比赛链接: https://atcoder.jp/contests/abc328
Print the total score for all problems with a score of X or less.
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int n,a; cin>>n>>a;
int ans = 0;
for(int i = 1; i <= n; i++){
int x; cin>>x;
if(x <= a) ans += x;
}
cout<<ans<<endl;
}考虑到$N$和$D$都很小....直接暴力判断一下是不是全一样就行了
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int n; cin>>n;
vector<int> d(n + 1);
int ans = 0;
for(int i = 1; i <= n; i++){
cin>>d[i];
if(i >= 10){
if(i % 10 != (i / 10) % 10) continue;
}
if(i == 100){
continue;
}
int now = (i % 10);
while(now <= d[i]){
ans++;
now = now * 10 + (i % 10);
}
}
cout<<ans<<endl;
}前缀和，可以发现一段中满足$l_i \leq p \leq r_i-1$ and $S_p = S_{p+1}$是递增的，而且前后不影响
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int n,q; cin>>n>>q;
string s; cin>>s; s = " " + s + " ";
vector<int> ct(n + 2);
ct[0] = 0;
for(int i = 1; i <= n; i++){
if(s[i] == s[i + 1]) ct[i] = ct[i - 1] + 1;
else ct[i] = ct[i - 1];
}
while(q--){
int l, r; cin>>l>>r;
cout<<ct[r - 1] - ct[l - 1]<<endl;
}
}模拟一个栈，检查后三位是不是'ABC'，是的话直接弹出
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
string s; cin>>s;
string st;
for(int i = 0; i < s.length(); i++){
st.push_back(s[i]);
if(st.length() < 3) continue;
if( st[st.length() - 3] == 'A' &&
st[st.length() - 2] == 'B' &&
st[st.length() - 1] == 'C'){
st = st.substr(0, st.length() - 3);
}
}
cout<<st<<endl;
}可以发现$N$特别小，加上是无向简单图，直接考虑暴力做法就行了。
暴力就是加点法去生成树
DFS里就是每次检查一下还有那些点没被连上，并且与已经被连上的点相邻，就可以连它
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100;
vector<int> G[N];
int W[N][N];
int vis[N];
int n,m,k;
int ans = 1e15 + 20;
int sum = 0;
void dfs(int ct){
for(int i = 1; i <= n; i++){
if(!vis[i]){
for(int j : G[i]){
if(vis[j]){
vis[i] = 1;
sum += W[i][j];
dfs(ct + 1);
sum -= W[i][j];
vis[i] = 0;
}
}
}
}
if(ct == n){
ans = min(ans, sum % k);
}
}
signed main(){
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
cin>>n>>m>>k;
for(int i = 1; i <= m; i++){
int u,v,w; cin>>u>>v>>w;
G[u].push_back(v); W[u][v] = w;
G[v].push_back(u); W[v][u] = w;
}
for(int i = 0; i < N; i++) vis[i] = 0;
vis[1] = 1;
sum = 0;
dfs(1);
cout<<ans<<endl;
}带权并查集，套板子就行了
这题主要的阻碍在于参照物太多了，每次给出的都是相对的属性，考虑用并查集确定统一的参照物以便于对比。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int pre[N];
int val[N];
int find(int x) {
if(x!=pre[x]) {
int t=pre[x];
pre[x]=find(pre[x]);
val[x]+=val[t];
}
return pre[x];
}
void merge(int x,int y,int s) {
if (find(x)!=find(y)) {
int t = find(x);
pre[find(x)]=find(y);
val[t]=val[y]-val[x]+s;
}
}
signed main(){
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
int n, q; cin>>n>>q;
set<int> ans;
for(int i = 1; i <= n; i++) pre[i] = i;
for(int i = 1; i <= q; i++){
int a,b,d; cin>>a>>b>>d;
int fa = find(a);
int fb = find(b);
if(fa != fb){
merge(a, b, d);
ans.insert(i);
} else {
if(val[a] - val[b] == d) ans.insert(i);
}
}
for(int i : ans){
cout<<i<<" ";
}
}