传送门:
https://atcoder.jp/contests/abc182
atcoder 好久没补了Orz,今天数据结构、马原课写了一下(
A
#include<bits/stdc++.h>
using namespace std;
int main(){
int a, b; cin>>a>>b;
cout<<2*a+100-b;
return 0;
}
B
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int w[N], n;
int main(){
cin>>n;
for(int i=1; i<=n; i++) cin>>w[i];
int len=0, res;
for(int i=2; i<=1000; i++){
int cnt=0;
for(int j=1; j<=n; j++) if(w[j]%i==0) cnt++;
if(cnt>len){
len=cnt;
res=i;
}
}
cout<<res;
return 0;
}
C
我去年十一月现场打过这个比赛,因此第一份是去年的(码风毒瘤)。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<list>
#include<cstdlib>
#include<set>
#include<map>
using namespace std;
typedef unsigned long long ll;
int main(){
string s;
while(cin>>s){
int rec1=0,rec2=0,rec3=0;
int sum=0;
for(int i=0;i<s.length();i++){
int cnt=s[i]-'0';
if(cnt %3 ==1) rec1++;
else if(cnt %3 ==2) rec2++;
else rec3++;
sum+=cnt;
}
int len=s.length();
//cout<<sum;
if(sum%3==0)cout<<0;
else{
if(len<=2 && !rec3) cout<<-1;
else if(!rec2){
if(sum%3==1) cout<<1;
else cout<<2;
}
else if(!rec1){
if(sum%3==2) cout<<1;
else cout<<2;
}
else{
cout<<1;
}
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int lowbit(int x){
return x&-x;
}
int cal(int x){
int res=0;
while(x) x-=lowbit(x), res++;
return res;
}
int main(){
string s; cin>>s;
int n=s.size();
int res=0;
for(int i=0; i<(1<<n); i++){
int r=0;
for(int j=0; j<n; j++) if(i>>j&1) r+=s[j]-'0';
if(r%3==0) res=max(res, cal(i));
}
if(!res) puts("-1");
else cout<<n-res<<endl;
return 0;
}
D
直接枚举前面走过的完整行对应的贡献 + 当前行最大前缀和(这个可以一边扫一边维护)。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;
#define int ll
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=2e5+5;
int n, w[N];
int f[N], mx[N];
signed main(){
read(n);
rep(i,1,n) read(w[i]), w[i]+=w[i-1];
int res=0;
rep(i,1,n){
if(i!=1) mx[i]=max(w[i], mx[i-1]);
else mx[i]=w[i];
int t=f[i-1]+mx[i];
res=max(res, t);
f[i]=w[i]+f[i-1];
}
cout<<res<<endl;
return 0;
}
E
从四个方向更新可以照到的地方。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=1550;
int n, m;
int w[N][N];
int g[4][N][N];
int main(){
read(n), read(m);
int u, v; read(u), read(v);
rep(i,1,u){
int x, y; read(x), read(y);
w[x][y]=1;
}
rep(i,1,v){
int x, y; read(x), read(y);
w[x][y]=-1;
}
rep(i,0,3) memcpy(g[i], w, sizeof g[i]);
rep(i,1,n) rep(j,1,m){
if(w[i][j]==-1) g[0][i][j]=0;
else if(g[0][i][j-1]==1 || w[i][j]==1) g[0][i][j]=1;
else if(w[i][j-1]==-1) g[0][i][j]=0;
}
rep(i,1,n) dwn(j,m,1){
if(w[i][j]==-1) g[1][i][j]=0;
else if(g[1][i][j+1]==1 || w[i][j]==1) g[1][i][j]=1;
else if(w[i][j+1]==-1) g[1][i][j]=0;
}
cerr<<g[1][3][1]<<endl;
rep(j,1,m) rep(i,1,n){
if(w[i][j]==-1) g[2][i][j]=0;
else if(g[2][i-1][j]==1 || w[i][j]==1) g[2][i][j]=1;
else if(w[i-1][j]==-1) g[2][i][j]=0;
}
rep(j,1,m) dwn(i,n,1){
if(w[i][j]==-1) g[3][i][j]=0;
else if(g[3][i+1][j]==1 || w[i][j]==1) g[3][i][j]=1;
else if(w[i+1][j]==-1) g[3][i][j]=0;
}
int res=0;
rep(i,1,n){
rep(j,1,m){
int t=0;
rep(x,0,3) t|=g[x][i][j];
res+=t;
}
}
cout<<res<<endl;
return 0;
}