2022 ICPC网络预选赛1

2022 ICPC网络预选赛1

A

最难的一点就是没有处理环形后效性

比如询问L=1R=9 ->111000111应该是长度为6的连续一段1,贡献为6/2=3而不是2+2=4

做法就是预处理L右边最近的0的下标x，预处理R左边最近的0的下标y，然后把一段区间分成三份求解，中间就直接贡献sum[y]-sum[x-1]

然后把左边和右边连续的1加起来除于2

做法1，dp处理前缀和贡献

#include
using namespace std;
const int N=1e6+10;
char s[N];
int n,m,sum[N],L[N],R[N];
int f[N],l,r;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>s+1;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')cnt++;
        else cnt=0;
        f[i]=f[i-cnt-1]+(cnt+1)/2;
    }
    L[0]=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')L[i]=L[i-1];
        else L[i]=i;
    }
    R[n+1]=n+1;
    for(int i=n;i>=1;i--){
        if(s[i]=='1')R[i]=R[i+1];
        else R[i]=i;
    }
    while(m--){
        cin>>l>>r;
        int len=r-l+1;
        int cnt1=r-L[r]+R[l]-l;
        int t=f[L[r]]-f[R[l]-1]+(cnt1+1)/2;
        cout<<max(0,len/3-t)<<'\n';
    }
}

做法2，对一段连续的1采取贡献差分，也就是+1+0+1+0+1+0，然后前缀和

这样可以保证奇数的时候上取整，偶数下取整

#include
using namespace std;
const int N=1e6+10;
char s[N];
int n,m,sum[N],L[N],R[N];
int cal(int l,int r){
    int ll=R[l];
    int rr=L[r];
    if(ll>=rr)return (r-l+1)/2;
    int len1=(r-rr)+(ll-l);
    return sum[rr]-sum[ll-1]+(len1+1)/2;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>s+1;
    // for(int i=1;i<=n;i++){
    //     if(s[i]=='1'&&s[i-1]!='1')sum[i]=1;
    //     sum[i]+=sum[i-1];
    // }
    int last=-1;
    for(int i = 1; i <= n ; i ++ ) 
    {
        if(s[i] == '1')
        {
            if(last != i - 1) sum[i] = 1, last = i;
            else last = -1;
        }
        sum[i] += sum[i - 1];
    }
    for(int i=1;i<=n;i++){
        if(s[i]=='0')L[i]=i;
        else L[i]=L[i-1];
    }
    R[n+1]=n+1;
    for(int i=n;i>=1;i--){
        if(s[i]=='0')R[i]=i;
        else R[i]=R[i+1];
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        int len=r-l+1;
        int t=cal(l,r);
        cout<<max(0,len/3-t)<<'\n';
    }
}

B

先预处理我要选x个tower的状态，pushback进vector里面

开一个优先队列对一个个时间片，先拿出来，t=t+a[i]，然后放进去

dfs爆搜

#include
using namespace std;
const int N=16,M=(1<<N)+10;
int n,a[N],b[N],ans=1e9;
vector<int>v[M];
typedef pair<int,int>PII;
priority_queue<PII,vector<PII>,greater<PII>>q;
#define t first
#define u second
int cal(int x){
    int ans=0;
    for(int i=0;i<n;i++)ans+=x>>i&1;
    return ans;
}
int dfs(int s,int T){
    if(s+1==1<<n)return T;
    int sum=0;
    T=q.top().t;
    while(q.size()&&q.top().t==T){
        int u=q.top().u;
        int t=q.top().t;
        sum+=b[u];
        q.pop();
        q.push({T+a[u],u});
    }
    if(sum+cal(s)>=n)return T;
    int ans=1e9;
    for(auto x:v[sum]){
        if(x&s)continue;
        for(int i=0;i<n;i++){
            if(x>>i&1)q.push({a[i]+T,i});
        }
        ans=min(ans,dfs(s|x,T));
    }
    return ans;
}
signed main(){
    cin>>n;
    for(int i=0;i<1<<n;i++){
        v[cal(i)].push_back(i);
    }
    for(int i=0;i<n;i++)cin>>a[i]>>b[i];
    for(int i=0;i<n;i++){
        while(q.size())q.pop();
        q.push({a[i],i});
        ans=min(ans,dfs(1<<i,0));
    }
    cout<<ans;
}

C

结论题，去理解题意，感受一下为什么

没有特判n==1wa了一发，没有清空度数数组wa了一发

D

我写的爆搜要剪很多枝才能刚好冲过去,vp的时候一直超时，改完就一发a了

而且代码很丑

说白了就是枚举长度len，枚举后缀零个数x，然后放一个1去挡，然后最前面也是一个1，dfs爆搜放y-2个1的情况，对询问二分

#include
using namespace std;
set<int>S;
int T,l,r,len;
int a[31];
// vectorans;
void dfs(int l,int r,int y){
    if(l>r){
        if(y==0){
            int x=0;
            for(int i=0;i<len;i++)x+=a[i]<<i;
            S.insert(x);
            return;
        }
        else return;
    }
    
    if(y==0){dfs(r+1,r,y);return;}
    if(y==r-l+1){
        for(int i=l;i<=r;i++)a[i]=1;
        dfs(r+1,r,0);
        for(int i=l;i<=r;i++)a[i]=0;
        return;
    }
    if(y>r-l+1)return;
    if(y)a[l]=1,dfs(l+1,r,y-1);
    a[l]=0,dfs(l+1,r,y);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    S.insert(2);
    for(len=4;len<=30;len++){
        for(int i=0;i<len;i++)a[i]=0;
        for(int x=2;x<=len/2;x++){
            for(int i=0;i<x;i++)a[i]=0;
            a[x]=1;
            a[len-1]=1;
            int y=x-2;//要放y个1
            dfs(x+1,len-2,y);
        }
    }
    cin>>T;
    while(T--){
        cin>>l>>r;
        auto it=S.lower_bound(l);
        if(it==S.end()||*it>r)cout<<"-1"<<'\n';
        else cout<<*it<<'\n';
    }
}

看到有个人写了个很优美的折半搜索

#include
using namespace std;
set<int>S;
int T,l,r,len;
int a[31];
void dfs(int x,int cnt,int p){
    if(cnt==0){
        if(x<=1e9)S.insert(x);
        return;
    }
    if(p==30)return;
    dfs(x|1<<p,cnt-1,p+1);
    dfs(x,cnt,p+1);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=1;i<=16;i++)dfs(1<<i,i-1,i+1);
    cin>>T;
    while(T--){
        cin>>l>>r;
        auto it=S.lower_bound(l);
        if(it==S.end()||*it>r)cout<<"-1"<<'\n';
        else cout<<*it<<'\n';
    }
}

G

没读题

感觉读懂硬搞能写

#include 
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 110;
ll dp[6][55][35][27][22], k[5], x[5], s[N];
int n, T;
 
int main()
{ 
    scanf("%d%d", &n, &T);
    _for(i, 1, 4)
    {
        scanf("%lld", &x[i]);
        k[i] = k[i - 1] + x[i];
    }
    _for(i, 1, n)
    {
        ll x; scanf("%lld", &x);
        s[i] = s[i - 1] + x;
    }
 
    ll ans = 0;
    _for(i, 1, n)
        _for(p1, 0, n / 2 + 1)
             _for(p2, 0, n / 3 + 1)
                _for(p3, 0, n / 4 + 1)
                    _for(p4, 0, n / 5 + 1)
                    {
                        if(p1 * k[1] + p2 * k[2] + p3 * k[3] + p4 * k[4] > T) break;
 
                        ll res = dp[(i - 1 + 6) % 6][p1][p2][p3][p4];
                        if(p1 - 1 >= 0 && i - 2 >= -1) res = max(res, dp[(i - 2 + 6) % 6][p1 - 1][p2][p3][p4] + s[i] - s[i - 1]);
                        if(p2 - 1 >= 0 && i - 3 >= -1) res = max(res, dp[(i - 3 + 6) % 6][p1][p2 - 1][p3][p4] + s[i] - s[i - 2]);
                        if(p3 - 1 >= 0 && i - 4 >= -1) res = max(res, dp[(i - 4 + 6) % 6][p1][p2][p3 - 1][p4] + s[i] - s[i - 3]);
                        if(p4 - 1 >= 0 && i - 5 >= -1) res = max(res, dp[(i - 5 + 6) % 6][p1][p2][p3][p4 - 1] + s[i] - s[i - 4]);
 
                        dp[i % 6][p1][p2][p3][p4] = res;
                        if(i == n) ans = max(ans, dp[i % 6][p1][p2][p3][p4]);
                    }
    printf("%lld\n", ans);
 
    return 0;
}

H

赛时沛桐过的，写个递归就好了，如果紧张的话很大概率写不好

#include
using namespace std;
#define int long long
const int mod=20220911;
int ans;
int dfs(){
    int ans=0;
    string s;
    while(cin>>s&&s!="for"){
        if(s[0]=='l')ans++;
        else if(s[0]=='r')ans+=dfs();
    }
    int x;
    cin>>x;
    return x*ans%mod;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string s;
    while(cin>>s&&s!="fin"){
        if(s[0]=='l')ans++;
        else if(s[0]=='r')ans+=dfs();
        ans%=mod;
    }
    cout<<ans;
}

J

非常好的期望题

根据样例猜构造方式，需要刷题量足够多足够敏感

设第一个为A，然后想到错位相消就很快了

记得特判算出来的A不合法的情况和超出范围的情况

#include
#define int long long
using namespace std;
int x,y,s,A,a,b,n,m;
signed main(){
    cin>>x>>y;
    for(int i=2;i<x;i++)s+=i;
    for(m=2;;m++){
        n=m-x+3;
        if(n<=1||n>m)continue;
        a=m*y-n*x+x-s;
        b=m-s-n*x+x;
        int d=__gcd(a,b);
        a/=d;
        b/=d;
        if(a*b<=0||a>b)continue;
        if(a>10000||b>10000)continue;
        cout<<a<<" "<<b<<'\n';
        for(int i=m;i>=n;i--)cout<<1<<" "<<i<<'\n';
        cout<<"1 1"<<'\n';
        return 0;
    }
}

L

赛时无法解决操作的前缀限制关系，即app，ppa会对应不同的方案，然后就不会了

结果发现题解是预处理了一个限制数组

，理解不是特别困难但就是想不到

#include
using namespace std;
const int N=5e5+10;
int f[N][30],vis[30],dont[30][30],n,m;
char a[N],b[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>a+1>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    for(int i=1;i<=m;i++){
        for(int j=0;j<26;j++){
            if(vis[j])dont[j][b[i]-'a']=1;
        }
        vis[b[i]-'a']=1;
    }
    for(int i=1;i<=n;i++)f[i][a[i]-'a']=1;
    for(int i=1;i<=n;i++){
        int x=a[i]-'a';
        if(!vis[x]){
            for(int j=0;j<26;j++)f[i][j]=f[i-1][j]+1;
        }
        else{
            for(int j=0;j<26;j++){
                f[i][j]=max(f[i][j],f[i-1][j]);
                if(dont[j][x])continue;
                f[i][x]=max(f[i][x],f[i-1][j]+1);
            }
        }
    }
    int ans=0;
    for(int j=0;j<26;j++)ans=max(ans,f[n][j]);
    cout<<ans;
}

感觉区域赛的dp还是非常考验大抽象级别的思维量，非常的灵活

比较有特点的是去年威海站的打砖块，某div2F题red and black

acwing宝藏和昨晚的cf#281 E题