A.
直接模拟即可
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
void solve()
{
int a,b,c;
cin>>a>>b>>c;
int res=0;
if(a==150) res++;
if(a==200) res+=2;
if(b==45) res+=2;
else if(b>=34) res++;
if(c==45) res+=2;
else if(c>=34) res++;
cout<<res<<"\n";
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
B
如果有两只猫同一个墙壁
那么只要放一个就行
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int x[N],y[N];
void solve()
{
cin>>n>>m>>k;
set<PII> st;
for(int i=1;i<=k;i++){
cin>>x[i]>>y[i];
st.insert({x[i],y[i]});
}
int res=4*k;
int cnt=0;
for(int i=1;i<=k;i++)
{
for(int j=0;j<4;j++){
int tx=x[i]+dx[j],ty=y[i]+dy[j];
if(st.count({tx,ty})) cnt++;
// st.insert({tx,ty});
}
}
cout<<res-cnt/2;
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
//cin>>t;
while(t--) solve();
}
C
因为是子序列,所以其实只要确定了
最大值最小值,能选的数就确定了
答案是2^(i-j-1)
但是这个n^n
考虑枚举最小值
我们把公式拆开
2^(i-1) / 2^(j)
因为我们是枚举最小值,即j已经知道了
那么我们只需要求前一个式子总和即可
总和就是在不超过k的情况下比a[j]大的数里面的2^(i-1)的总和
所以我拿了个sum记录这个总和
排序后边删边求即可跑一遍字典树
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int fact[N],infact[N];
int tr[N*25][2],idx,sum[N*30];
int qp2[N],a[N];
int qmi(int a,int k,int p){
int res=1;
while(k){
if(k&1) res=(LL) res*a%p;
a=(LL)a*a%p;
k>>=1;
}
return res;
}
void init(){
qp2[0]=fact[0]=infact[0]=1;
for(int i=1;i<N;i++){
qp2[i]=qp2[i-1]*2%mod;
fact[i]=(LL)fact[i-1]*i%mod;
infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;
}
}
int C(int a,int b){
if(b<0||b>a) return 0;
return ((LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
int inv(int x){
return qmi(x,mod-2,mod);
}
void add(int x,int v){
int p=0;
for(int i=31;i>=0;i--){
sum[p]=(sum[p]+qp2[v])%mod;
int g=x>>i&1;
if(!tr[p][g])
{
tr[p][g]=++idx;
sum[idx]=tr[idx][0]=tr[idx][1]=0;
}
p=tr[p][g];
}
sum[p]=(sum[p]+qp2[v])%mod;
}
void del(int x,int v){
int cur=0;
for(int i=31;i>=0;i--){
sum[cur]=(sum[cur]-qp2[v]+mod)%mod;
int g=x>>i&1;
cur=tr[cur][g];
}
sum[cur] = (sum[cur] - qp2[v] + mod) % mod;
}
int query(int x){
int cur=0;
int res=0;
for(int i=31;i>=0;i--)
{
int g=x>>i&1;
if((k>>i&1)&&tr[cur][(x>>i&1)])
{
res=(res+sum[tr[cur][(x>>i&1)]])%mod;
}
if(k>>i&1){
if(tr[cur][g^1]) cur=tr[cur][g^1];
else return res;
}
else{
if(tr[cur][g]) cur=tr[cur][g];
else return res;
}
}
res=(res+sum[cur])%mod;
return res;
}
void solve()
{
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
tr[0][0]=tr[0][1]=sum[0]=idx=0;
for(int i=0;i<n;i++)
add(a[i],i);
//2^(i-j-1)
//a[i]为min时候
//2^i-
int res=n;
for(int i=0;i<n;i++){
del(a[i],i);
int g=query(a[i]);
res=(res+g*inv(qp2[i+1])%mod);
res%=mod;
}
cout<<res<<"\n";
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
init();
cin>>t;
while(t--) solve();
}
D
dp
方程为使用前i张卡牌,且当前位置到j的最小值,我第三层是枚举使用了k张卡牌,需要这里优化一下不然会tle
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int a[N],f[2010][5010],b[N];
void solve()
{
int x;
cin>>n>>m>>x;
x--;
vector<int> mp(n+10,inf);
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i];
mp[a[i]]=min(mp[a[i]],b[i]);
}
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++)
f[i][j]=inf;
}
int lst=f[0][0];
f[0][x]=0;
int i=0;
for(int ii=1;ii<=n;ii++)
{
if(mp[ii]==inf) continue;
++i;
int a1=ii,b1=mp[ii];
for(int j=0;j<n;j++)
{
unordered_set<int> st;
for(int k=0;k<=n;k++)
{
if(k*b1>=f[i][j]) break;
int now=(j-k*a1)%n;
now=(now+n)%n;
f[i][j]=min(f[i][j],k*b1+f[i-1][now]);
}
}
}
if(f[i][n-1]==inf) f[i][n-1]=-1;
cout<<f[i][n-1]<<"\n";
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
E
考虑dp消灭后面i张卡牌需要的最小代价,显然我们需要枚举i+1到下一张相同a[i]的卡牌的位置的最小值+1
我这里直接用线段树求最值了0.0
贴板子比较快
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N];
class segment{
#define lson (u << 1)
#define rson (u << 1 | 1)
public:
int n;
vector<int> mn;
segment(int _n) : n(_n) {
mn.resize(n*4+10);
build(1,1,n);
}
void pushup(int u){
mn[u]=min(mn[lson],mn[rson]);
}
void build(int u, int l, int r){
if (l == r)
{
mn[u]=inf;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, int x, int val){
if (l==r&&x==l)
{
mn[u]=min(mn[u],val);
return;
}
int mid = (l + r) >> 1;
if (x<= mid) modify(lson, l, mid, x, val);
else modify(rson, mid + 1, r,x, val);
pushup(u);
}
int query(int u, int l, int r, int L,int R){
if (L<=l&&r<=R)
{
return mn[u];
}
int mid = (l + r) >> 1;
int res=inf;
if (L<= mid) res=query(lson, l, mid, L,R);
if(R>mid) res=min(res,query(rson, mid + 1, r,L, R));
return res;
}
};
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
vector<int> f(n+10,inf);
vector<int> nxt(n+10,0);
segment tr(n);
tr.modify(1,1,n,n,1);
f[n]=1;
nxt[a[n]]=n;
for(int i=n-1;i>=1;i--)
{
f[i]=f[i+1]+1;
if(nxt[a[i]]==0)
{
f[i]=1;
}
else f[i]=min(f[i],1+tr.query(1,1,n,i+1,nxt[a[i]]));
tr.modify(1,1,n,i,f[i]);
// cout<<i<<" "<<tr.query(1,1,n,i+1,nxt[a[i]])<<" "<<f[i]<<"\n";
// cout<<f[i]<<"\n";
// for(int j=i+1;j<=nxt[a[i]];j++)
// {
// f[i]=min(f[i],f[j]+1);
// }
nxt[a[i]]=i;
}
cout<<f[1]<<"\n";
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
F同理
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N];
class segment{
#define lson (u << 1)
#define rson (u << 1 | 1)
public:
int n;
vector<int> mn;
segment(int _n) : n(_n) {
mn.resize(n*4+10);
build(1,1,n);
}
void pushup(int u){
mn[u]=min(mn[lson],mn[rson]);
}
void build(int u, int l, int r){
if (l == r)
{
mn[u]=inf;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, int x, int val){
if (l==r&&x==l)
{
mn[u]=min(mn[u],val);
return;
}
int mid = (l + r) >> 1;
if (x<= mid) modify(lson, l, mid, x, val);
else modify(rson, mid + 1, r,x, val);
pushup(u);
}
int query(int u, int l, int r, int L,int R){
if (L<=l&&r<=R)
{
return mn[u];
}
int mid = (l + r) >> 1;
int res=inf;
if (L<= mid) res=query(lson, l, mid, L,R);
if(R>mid) res=min(res,query(rson, mid + 1, r,L, R));
return res;
}
};
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
vector<int> f(n+10,inf);
vector<int> nxt(n+10,0);
segment tr(n);
tr.modify(1,1,n,n,1);
f[n]=1;
nxt[a[n]]=n;
for(int i=n-1;i>=1;i--)
{
f[i]=f[i+1]+1;
if(nxt[a[i]]==0)
{
f[i]=1;
}
else f[i]=min(f[i],1+tr.query(1,1,n,i+1,nxt[a[i]]));
tr.modify(1,1,n,i,f[i]);
// cout<<i<<" "<<tr.query(1,1,n,i+1,nxt[a[i]])<<" "<<f[i]<<"\n";
// cout<<f[i]<<"\n";
// for(int j=i+1;j<=nxt[a[i]];j++)
// {
// f[i]=min(f[i],f[j]+1);
// }
nxt[a[i]]=i;
}
cout<<f[1]<<"\n";
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
G
因为都是正数所以如果找到了切割点
那么当前点左边全选,当前点用来减去
题目意思式子就是找到最大的
(sum[r]-sum[l-1])-2a[r]
=sum[r]-2a[r]
sum[l-1]可以用线段树区间求和解决
sum[r]-2*a[r]也可以用线段树求区间最大值解决
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N],s[N];
class segment{
#define lson (u << 1)
#define rson (u << 1 | 1)
public:
int n;
vector<int> sum,mx,add;
segment(int _n) : n(_n) {
sum.resize(n*4+10);
mx.resize(n*4+10);
add.resize(n*4+10);
build(1,1,n);
}
void pushup(int u){
mx[u]=max(mx[lson],mx[rson]);
sum[u]=sum[lson]+sum[rson];
}
void pushdown(int u){
if(add[u]){
mx[lson]+=add[u];
mx[rson]+=add[u];
add[lson]+=add[u];
add[rson]+=add[u];
add[u]=0;
}
}
void build(int u, int l, int r){
if (l == r)
{
mx[u]=s[l]-2*a[l];
sum[u]=a[l];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, int L,int R, int val,int op){
if (L<=l&&r<=R)
{
if(op==1) sum[u]=val;
else{
mx[u]+=val;
add[u]+=val;
}
return;
}
pushdown(u);
int mid = (l + r) >> 1;
if (L<= mid) modify(lson, l, mid, L,R, val,op);
if(R>mid) modify(rson, mid + 1, r,L,R, val,op);
pushup(u);
}
int querysum(int u, int l, int r, int L, int R)
{
if(L<=l&&r<=R){
return sum[u];
}
pushdown(u);
int mid=l+r>>1;
int res=0;
if(L<=mid) res+=querysum(u<<1,l,mid,L,R);
if(R>mid) res+=querysum(u<<1|1,mid+1,r,L,R);
return res;
}
int querymx(int u, int l, int r, int L, int R)
{
if(L<=l&&r<=R){
return mx[u];
}
pushdown(u);
int mid=l+r>>1;
int res=-inf;
if(L<=mid) res=querymx(u<<1,l,mid,L,R);
if(R>mid) res=max(res,querymx(u<<1|1,mid+1,r,L,R));
return res;
}
};
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
segment tr(n);
while(m--){
int op;
cin>>op;
if(op==1){
int x,y;cin>>x>>y;
tr.modify(1,1,n,x,x,2*a[x]-2*y,2);
tr.modify(1,1,n,x,n,y-a[x],2);
a[x]=y;
tr.modify(1,1,n,x,x,a[x],1);
}
else{
int l,r;cin>>l>>r;
int res=tr.querymx(1,1,n,l+1,r);
if(l-1!=0)
res-=tr.querysum(1,1,n,1,l-1);
cout<<res<<"\n";
}
}
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
H
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const long long inf=1e18;
int n,m,k;
int a[N];
struct node{
int a[8];
node(){memset(a,0,sizeof(a));}
}tr[N*4];
node f(int x){
node w;
w.a[0]=-x;
w.a[1]=-inf;
w.a[2]=x;
w.a[3]=-inf;
w.a[4]=x;
w.a[5]=-x;
w.a[6]=-inf;
w.a[7]=-inf;
return w;
}
node merge(node l,node r){
node f;
f.a[0]=max(l.a[0],l.a[5]+r.a[0]);
f.a[1]=max({l.a[1],l.a[6]+r.a[0],l.a[4]+max(r.a[1],r.a[0])});
f.a[2]=max({r.a[2],r.a[4]+l.a[2]});
f.a[3]=max({r.a[3],r.a[5]+max(l.a[2],l.a[3]),l.a[2]+r.a[6]});
f.a[4]=l.a[4]+r.a[4];
f.a[5]=l.a[5]+r.a[5];
f.a[6]=max({l.a[4]+r.a[5],l.a[6]+r.a[5],l.a[4]+r.a[6]});
f.a[7]=max({l.a[7],r.a[7],r.a[0]+max(l.a[2],l.a[3]),
l.a[2]+max(r.a[0],r.a[1])});
return f;
}
//0 pre- 乘上-1的前缀最大值
//1 pre+- 前面+(-后面)
//2 suf+
//3 suf+-
//4 tot+ 总和
//5 tot-
//6 tot+-
//7 ans
void build(int u,int l,int r){
if(l==r){
tr[u]=f(a[l]);
return ;
}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
tr[u]=merge(tr[u<<1],tr[u<<1|1]);
}
void modify(int u,int l,int r,int x,int v){
if(l==r){
tr[u]=f(v);
return ;
}
int mid=l+r>>1;
if(x<=mid) modify(u<<1,l,mid,x,v);
else modify(u<<1|1,mid+1,r,x,v);
tr[u]=merge(tr[u<<1],tr[u<<1|1]);
}
node query(int u,int l,int r,int L,int R){
if(l>=L&&r<=R){
return tr[u];
}
int mid=l+r>>1;
if(L<=mid&&R>mid) return merge(query(u<<1,l,mid,L,R),query(u<<1|1,mid+1,r,L,R));
if(L<=mid) return query(u<<1,l,mid,L,R);
return query(u<<1|1,mid+1,r,L,R);
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--){
int op;
cin>>op;
if(op==1){
int x,y;cin>>x>>y;
modify(1,1,n,x,y);
a[x]=y;
}
else{
int l,r;cin>>l>>r;
cout<<query(1,1,n,l,r).a[7]<<"\n";
}
}
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
I
考虑拆掉绝对值
if au>av au+av+au-av=2au
else au+av-au+av=2av
然后又由于我们点u和点v是固定要走到的,我们中间不会再走其他点
因为是求经过的点的max,必经点确定了其他点能不走就不走
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int a[N];
void solve()
{
cin>>n;
vector<int> s(n+10);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
int res=0;
for(int i=1;i<=n;i++)
{
res+=(i-1)*a[i];
res+=s[n]-s[i];
// for(int j=1;j<=n;j++)
// {
// if(i==j) continue;
// res+=max(a[i],a[j]);
// }
}
cout<<res*2<<"\n";
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
J
考虑同理上面式子推导
得出答案是min(a[u],a[v])2
但是这个是取min
所以我们还可以走其他点,贪心的走最小值点a[1],那么让a[1]做中间点,那么他的代价是2(2*a[1])
我这里做法是直接枚举哪些点后面需要经过a[1]点,然后讨论一下就行了
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int a[N];
void solve()
{
cin>>n;
vector<int> s(n+10);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
int res=0;
int lst=n;
res+=a[1]*2*(n-1);
while(lst>=1&&a[lst]*2>=a[1]*2*2)
{
lst--;
}
for(int i=2;i<=n;i++)
{
int now=res;
if(lst<i){
res+=(n-lst)*a[1]*2*2;
res+=2*s[lst];
res-=min(a[1]*2,a[i])*2;
}
else{
res+=(n-i)*2*a[i];
res+=2*s[i-1];
}
}
cout<<res<<"\n";
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
K
考虑a b c d _最多5个
所以直接dfs模拟就行
//x没前导0
//x是8的倍数
//x<=y
//小写字母的数字一定相同,不同的字母数字一定不同
//_可以任意一个
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
string a,b;
int res=0;
vector<char> c;
unordered_map<char,int> mp;
void dfs(int u){
if(u==c.size()){
string x=a;
for(auto&xx:x)
{
if(xx=='a'||xx=='b'||xx=='c'||xx=='d'||xx=='_'){
xx=mp[xx]+'0';
}
}
if(x[0]=='0'&&x.size()!=1) return ;
int now=0,now1=0;
for(auto&xx:b) now1=now1*10+(xx-'0');
for(auto&xx:x) now=now*10+(xx-'0');
if(now%8!=0||now>now1) return ;
//cout<<now<<" "<<now1<<"\n";
res++;
return ;
}
for(int i=0;i<=9;i++)
{
if(c[u]!='_')
{
bool flag=true;
for(int j=0;j<u;j++){
if(c[j]=='_') continue;
if(mp[c[j]]==i) flag=false;
}
if(!flag) continue;
}
mp[c[u]]=i;
dfs(u+1);
}
}
void solve()
{
cin>>n;
cin>>a>>b;
c.clear();
for(int i=0;i<a.size();i++)
{
if(a[i]=='a'||a[i]=='b'||a[i]=='c'||a[i]=='d'||a[i]=='_'){
c.push_back(a[i]);
}
}
sort(c.begin(),c.end());
c.erase(unique(c.begin(),c.end()),c.end());
res=0;
if(c.size())
dfs(0);
else{
int now=0,now1=0;
for(auto&xx:a) now1=now1*10+(xx-'0');
for(auto&xx:b) now=now*10+(xx-'0');
if(now1<=now&&now1%8==0) res=1;
if(a.size()!=1&&a[0]=='0') res=0;
}
cout<<res%mod<<"\n";
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
L
M