生日打了场Atcoder Beginner还可以吧……做出了前四道题，第五、六题是dp方程没想出来QwQ
A - Apple
水题+1，感谢atcoder把坑都亮出来QwQ……
分两种情况讨论：三个一卖的比（一个一卖的）× 3 的贵和另一种正常算的，注意买且仅买n个
#include<bits/stdc++.h>
using namespace std;
int main(){
int x,y,n;cin>>x>>y>>n;
if(x*3<=y)cout<<n*x<<endl;
else{
int a=n/3,b=n%3;
cout<<a*y+b*x<<endl;
}
return 0;
}
B - Explore
水题+1，直接过一遍n，算T-ai+bi小于零直接挂掉
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long t,a[100010],b[100010];
int main(){
cin>>n>>m>>t;
for(int i=1;i<n;i++)cin>>a[i];
for(int i=1;i<=m;i++){int id;cin>>id;cin>>b[id];}
for(int i=1;i<n;i++){
t=t-a[i]+b[i];
if(t<=0){cout<<"No"<<endl;return 0;}
}
cout<<"Yes"<<endl;
return 0;
}
C - Belt Conveyor
水题+3？直接跟着过一遍，记得flag数组做标记，如果已经来过就输出-1，动不了了输出所在坐标
#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[510][510];
bool fl[510][510];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){cin>>c[i][j];fl[i][j]=0;}
int x=1,y=1;
while(1){
if(fl[x][y]==1){cout<<-1<<endl;return 0;}
fl[x][y]=1;
if(c[x][y]=='U'&&x!=1)x--;
else if(c[x][y]=='D'&&x!=n)x++;
else if(c[x][y]=='L'&&y!=1)y--;
else if(c[x][y]=='R'&&y!=m)y++;
else{cout<<x<<" "<<y<<endl;return 0;}
}
}
D - Iroha and Haiku (New ABC Edition)
卡着线过QwQ
前缀和^_^ 先判断整体有没有可能，先找出x和w，过一遍[x,w]找符合要求的y,z，记得剪枝：）
#include<bits/stdc++.h>
using namespace std;
long long n,p,q,r,a[200010],b[200010],x,y,z,w;
int main(){
cin>>n>>p>>q>>r;
long long k=p+q+r;
for(long long i=1;i<=n;i++){cin>>a[i];b[i]=b[i-1]+a[i];}
if(b[n]<p+q+r){cout<<"No"<<endl;return 0;}
int l=1;
for(long long i=1;i<=n;i++){
if(b[i]>=k){
x=0;
for(;l<i;l++){
if(b[i]-b[l-1]<k)break;
if(b[i]-b[l-1]==k){x=l;break;}
}
if(i-x>=2&&x!=0){
int fl=0;
for(int j=x;j<=i;j++){
if(fl==0){
if(b[j]-b[x-1]>p)break;
if(b[j]-b[x-1]==p){y=j;fl++;}
}
else if(fl==1){
if(b[j]-b[y]>q)break;
if(b[j]-b[y]==q){z=j;fl++;break;}
}
}
if(fl==2){cout<<"Yes"<<endl;return 0;}
}
}
}
cout<<"No"<<endl;
}
E - Warp
考完了才整出来ε(┬┬﹏┬┬)3
把障碍物的坐标存在一个集合里，检查是否有可能在O（logM）时间内传送到某个点
首先，考虑以下较简单的问题：
进行两种传送，（x+1，y）和（x，y+1）其他条件相同；用动规来解决，其中DP[n][x][y]等于在n次隐形传送后最终到达（x，y）的路径数具体见代码:)
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int p[2][305][305];
set<pair<long long,long long>>s;
int main(){
int n,m;cin>>n>>m;
long long a,b,c,d,e,f;cin>>a>>b>>c>>d>>e>>f;
long long dxy[3][2]={{a,b},{c,d},{e,f}};
for(int i=1;i<=m;i++){long long x,y;cin>>x>>y;s.insert({x,y});}
p[0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
for(int k=0;k<=i;k++){
if(j+k>i) continue;
int t=i-j-k;
long long nx=j*a+k*c+t*e,ny=j*b+k*d+t*f;
for(int q=0;q<3;q++){
long long x=dxy[q][0],y=dxy[q][1];
if(s.find({x+nx,y+ny})==s.end())
p[i+1&1][j+(q==0)][k+(q==1)]=(p[i+1&1][j+(q==0)][k+(q==1)]+p[i&1][j][k])%mod;
}
}
}
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++)p[i&1][j][k]=0;
}
int res=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
if(i+j<=n)res=(res+p[n&1][i][j])%mod;
cout<<res<<endl;
return 0;
}
F - Manhattan Cafe
根本没看o(TヘTo)
dp++
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,d,f[1100][1100],a[110],b[110],ans;
int main(){
cin>>n>>d,f[0][0]=1;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int o=1,res;o<=n;o++)
for(int i=d;~i;i--)
for(int j=d;~j;j--){
if(!f[i][j])continue;
res=f[i][j];
for(int k=max(a[o]-(d-i),b[o]-(d-j));k<=min(a[o]+(d-i),b[o]+(d-j));k++)
(f[i+abs(k-a[o])][j+abs(k-b[o])]+=res)%=mod;
f[i][j]=(f[i][j]+mod-res)%mod;
}
for(int i=0;i<=d;i++)
for(int j=0;j<=d;j++)ans=(ans+f[i][j])%mod;
cout<<ans<<'\n';
return 0;
}
G - 012 Inversion
用一个可持久化段树在总共O（N+QlogN）个时间内解决
线段树的每个节点存储对应段的以下6个值:
- 0的个数
- 1的个数
- 2的个数
- （1，0）的个数
- （2，0）的个数
- （2，1）的个数
详情见代码：）
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using S = array<array<ll, 3>, 3>;
using F = array<short, 3>;
S op(S l, S r){
S res;
for(short i = 0; i < 3; i++)
for(short j = 0; j < 3; j++){
res[i][j] = l[i][j] + r[i][j];
if(i != j)
res[i][j] += l[i][i] * r[j][j];
}
return res;
}
S e(){
S res;
for(short i = 0; i < 3; i++)
for(short j = 0; j < 3; j++)res[i][j] = 0;
return res;
}
S mapping(F l, S r){
S res = e();
for(short i = 0; i < 3; i++){
res[l[i]][l[i]] += r[i][i];
for(short j = 0; j < 3; j++)
if(l[i] != l[j])res[l[i]][l[j]] += r[i][j];
}
return res;
}
F composition(F l, F r){
F res;
for(short i = 0; i < 3; i++)res[i] = l[r[i]];
return res;
}
F id() { return F{0, 1, 2}; }
int main(){
int N, Q;
scanf("%d %d", &N, &Q);
vector<S> A(N, e());
for(int i = 0; i < N; i++){
short a;
scanf("%hd", &a);
A[i][a][a] = 1;
}
lazy_segtree<S, op, e, F, mapping, composition, id> seg(A);
for(int _ = 0; _ < Q; _++){
short t;
int L, R;
scanf("%hd %d %d", &t, &L, &R);
L--;
if(t == 1){
S res = seg.prod(L, R);
ll ans = res[1][0] + res[2][0] + res[2][1];
printf("%lld\n", ans);
}else{
short S, T, U;
scanf("%hd %hd %hd", &S, &T, &U);
seg.apply(L, R, {S, T, U});
}
}
return 0;
}
标签：AtCoder,short,Beginner,Contest,int,res,long,++,using From： https://www.cnblogs.com/nancychai/p/16611384.html