HDU 2019三月校赛题解

由 Edwiv 发布于  ｜  50,447次浏览

这场一开始脑子还清楚，20分钟a了两题，博弈那道题属于简单题，但是后来因为1009用了string中的substr骚操作一直tle，后来改写的kmp才过的（赛后发现是memset的锅）

1007和1003也是可做题，场上写了一遍1003tle了之后就没去想了，以为有别的更高级的做法，没想到只是bfs时机不对，真是菜的真实；1007异或那题想到了随机性和n%2==1的情况，可惜还有15分钟写不出来偶数了。

下次再接再厉！



签到题，四个if就可以了

#include<bits/stdc++.h>
using namespace std;
#define maxn (int(1e5)+100)
#define mod ((int)1e9+7)
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define lll lon long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define pb push_back
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        string s1,s2;
        cin>>s1>>s2;
        int flag=1;
        for(int i=0;i<n;++i){
            if(s1[i]=='0'){
                if(s2[i]=='0'||s2[i]=='O')continue;
                else flag=0;
            }
            else if(s1[i]=='O'){
                if(s2[i]=='0'||s2[i]=='O')continue;
                else flag=0;
            }
            else if(s1[i]=='l'){
                if(s2[i]=='l'||s2[i]=='I')continue;
                else flag=0;
            }
            else if(s1[i]=='I'){
                if(s2[i]=='l'||s2[i]=='I')continue;
                else flag=0;
            }
            else{
                if(s2[i]!=s1[i]) flag=0;
            }
        }
            if(flag) cout<<"OK\n";
            else cout<<"NO\n";
        }
    }

待补

哎，赛前那天晚上才刚做了一道cf的连通块的题目，赛场上就不会了？？

其实只要用并查集将所有边的两端点合并，之后检查有没有点的度>2，有的话肯定为0（因为一个点最多连两种颜色）；那么剩下的就只有两种情况了，一种是链，一种是环，而奇数点的环肯定是不行的，偶数环和链的话就只会出现两种可能性，所以只要ans*=2就可以了。

并查集判环只需要在join时看看这个点之前有没有加过就可以了，加过的话肯定是环

#include<bits/stdc++.h>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ll long long
#define PI acos(1.0)
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n,m;
int pre[maxn],tot[maxn];
int num[maxn],vis[maxn];
void init(int n){
    for(int i=1;i<=n;++i){
        pre[i]=i;
        tot[i]=1;
        vis[i]=0;
        num[i]=0;
    }
}
int find(int x){
    while(x!=pre[x]){
        pre[x]=pre[pre[x]];
        x=pre[x];
    }
    return x;
}
void join(int x,int y){
    x=find(x);y=find(y);
    if(x!=y){
        if(x>y){
            pre[x]=y;
            tot[y] += tot[x];
        }
        else{
            pre[y]=x;
            tot[x] += tot[y];
        }
    }
    else vis[x]=1;//是环
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        init(n);
        int flag=0;
        for(int i=0;i<m;++i){
            int x,y;scanf("%d%d",&x,&y);
            if(!flag){
                num[x]++;num[y]++;
                join(x,y);
                if(num[x]>2||num[y]>2){
                    flag=1;
                    printf("0\n");
                }
            }
        }
        if(flag) continue;
        ll ans=1;
        for(int i=1;i<=n;++i){
            if(i==pre[i]&&num[i]){
                if(vis[i]){
                    if(tot[i]%2==0) ans*=2;
                    else{
                        flag=1;
                        printf("0\n");
                        break;
                    }
                }
                else{
                    ans*=2;
                }
                ans%=mod;
            }
        }
        if(flag) continue;
        if(ans==1) printf("0\n");
        else printf("%lld\n",ans%mod);
    }
}

dfs也是可以做的，时间复杂度也差不多

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int maxn = int(1e5)+100;
const int mod = int(1e9)+7;
int n,m,flag;
int vis[maxn],num[maxn];
vector<int> g[maxn];
ll ans=1;
void dfs1(int x,int fa){
    vis[x]=1;
    if(g[x].size()==1){
        if(g[x][0]==fa){
            ans*=2;ans%=mod;return;
        }
        else dfs1(g[x][0],x);
    }
    else if(g[x].size()==2){
        for(int i=0;i<g[x].size();++i){
            if(g[x][i]!=fa){
                dfs1(g[x][i],x);
            }
        }
    }
}
void dfs2(int x,int fa,int tot){
    if(flag) return;
    vis[x]=1;
    if(fa==0){
        dfs2(g[x][0],x,tot+1);
    }
    else{
        for(int i=0;i<g[x].size();++i){
            if(g[x][i]!=fa){
                if(vis[g[x][i]]){
                    if(tot%2==0){
                        ans*=2;ans%=mod;return;
                    }
                    else{
                        ans=1;flag=1;return;
                    }
                }
                else{
                    dfs2(g[x][i],x,tot+1);
                }
            }
        }
    }
}
void init(int n){
    for(int i=1;i<=n;++i){
        vis[i]=0;num[i]=0;g[i].clear();
    }
    flag=0; ans=1;
}
int main(){
    quickcin
    int t;cin>>t;
    while(t--){
        cin>>n>>m;
        init(n);
        while(m--){
            int u,v;cin>>u>>v;
            if(!flag){
                g[u].pb(v); g[v].pb(u);
                num[u]++;num[v]++;
                if(num[u]>2||num[v]>2){
                    flag=1;
                    cout<<"0\n";
                }
            }
        }
        if(flag) continue;
        for(int i=1;i<=n;++i){
            if(vis[i]||num[i]==0) continue;
            if(num[i]==1){
                dfs1(i,i);
            }
        }
        for(int i=1;i<=n;++i){
            if(vis[i]||num[i]==0) continue;
            if(num[i]==2){
                dfs2(i,0,1);
                if(flag){
                    cout<<"0\n";
                    break;
                }
            }
        }
        if(flag) continue;
        if(ans==1) cout<<"0\n";
        else cout<<ans%mod<<endl;
    }
}

暴力找循环节，找到后模拟，注意需要处理循环节内最大减小金额的情况

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define INF 0x3f3f3f3f
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
ll a[maxn];ll vis[maxn];
int n;
ll work(ll cur){
    for(int i=0;i<=n;++i) vis[i]=-1;
    ll res=0,nex,index=0;
    ll pos[maxn];
    while(1){
        res++; nex=cur%n;
        if(vis[nex]!=-1){
            if(cur>=vis[nex]) return -1;
            else break;
        }
        if(cur+a[nex]>=0){
            vis[nex]=cur;
            cur+=a[nex];
            pos[index++]=nex;
        }
        return res;
    }
    ll cost=vis[nex]-cur;//每个循环节减少金额
    ll len=0;ll maxd=INF;
    ll pre=0;//循环节开始下标
    for(int i=0;i<index;++i){
        if(pos[i]==nex) {
            len=index-i;//循环节长度
            pre=i;
            break;
        }
    }
    ll tem=0;
    for(ll i=pre;i<index;++i){
        tem+=a[pos[i]];
        maxd=min(maxd,tem);//循环节最大减少量
    }
    res+=(cur+maxd)/cost*len;
    cur-=(cur+maxd)/cost*cost;
    while(1){
        nex=cur%n; cur+=a[nex];
        if(cur<0) return res;
        res++;
    }
    return -1;
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        ll k;scanf("%d%lld",&n,&k);
        for(int i=0;i<n;++i) scanf("%lld",&a[i]);
        printf("%lld\n",work(k));
    }
}

 

三分题，对于[l,r]区间三分k，然后做一遍0-1背包，求出最小值即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int maxn = int(1e5)+100;
const int mod = int(1e9)+7;
ll a[550],b[550],w[550];
int n,bag,l,r;
ll calc(int x){
    ll v[550];
    for(int i=0;i<n;++i){
        v[i]=x*a[i]+b[i];
    }
    ll dp[550];mst(dp,0);
    for(int i=0;i<n;i++)
        for(int j=bag;j>=w[i];--j){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    return dp[bag];
}
int main(){
    quickcin
    int t;cin>>t;
    while(t--){
        cin>>n>>bag>>l>>r;
        for(int i=0;i<n;++i){
            cin>>a[i]>>b[i]>>w[i];
        }
        while(l+1<r){
            int lm=(l+r)>>1,rm=(lm+r)>>1;
            if(calc(lm)>calc(rm)) l=lm;
            else r=rm;
        }
        cout<<calc(r)<<endl;
    }
}

辣鸡BFS，比赛的时候没想出来要在修改的时候bfs，直接在询问时bfs，妥妥的t；


正解是每次修改进行一次bfs记录所有点的距离

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PI acos(1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n,m;
int vis[100][100],dis[100][100],g[100][100];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct pos{
    int x,y,st;
};
int ck(int x,int y){
    if(x<1||x>n||y<1||y>m||vis[x][y]||g[x][y])
        return 0;
    return 1;
}
void bfs(){
    mst(dis,-1);mst(vis,0);
    queue<pos> q;
    pos cur,nex;
    cur.x=1;cur.y=1;cur.st=0;vis[1][1]=1;
    q.push(cur);
    while(!q.empty()){
        cur=q.front();q.pop();
        dis[cur.x][cur.y]=cur.st;
        rep(i,0,3){
            nex.x=cur.x+dx[i];
            nex.y=cur.y+dy[i];
            nex.st=cur.st+1;
            if(ck(nex.x,nex.y)){
                q.push(nex);vis[nex.x][nex.y]=1;
            }
        }
    }
}
int main(){
    int t;scanf("%d",&t);
    while(t--){
        mst(vis,0);mst(dis,-1);mst(g,0);
        int q;
        scanf("%d%d%d",&n,&m,&q);
        int flag=1;
        while(q--){
            char c[2];int x,y;
            scanf("%s%d%d",c,&x,&y);
            if(c[0]=='?'){
                if(flag){
                    bfs();
                    flag=0;
                }
                cout<<dis[x][y]<<endl;
            }
            else{
                flag=1;
                g[x][y]=1;
            }
        }
    }
}

对于所有的原串和混淆过的串，求出他们每一位二进制中1的总数，再去对比1的数量，如果上下一样的话，那么k的这一位二进制取0（0^1=1），否则只能为1


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PI acos(1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int a[50],b[50];
        mst(a,0);mst(b,0);
        for(int i=0;i<n;++i){
            int x;cin>>x;
            int pos=0;
            while(x){
                a[pos++]+=(x%2);
                x/=2;
            }
        }
        for(int i=0;i<n;++i){
            int x;cin>>x;
            int pos=0;
            while(x){
                b[pos++]+=(x%2);
                x/=2;
            }
        }
        ll ans=0;
        for(int i=0;i<45;++i){
            if(a[i]!=b[i]){
                ans+=(int)pow(2,i);
            }
        }
        cout<<ans<<endl;
    }
}

博弈论，首先我们想，如果没有绿色卡组，那么每人每次只取一张是最优策略，此时只要红色卡片总数大于蓝色就必胜；加上绿色卡片之后，显然两人要先去取绿色的，谁先不能取了在去取自己的颜色，那这就是一个很简单的nim游戏。

#include<bits/stdc++.h>
using namespace std;
#define maxn (int(1e5)+100)
#define mod ((int)1e9+7)
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define lll lon long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define pb push_back
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int sum=0;
        int totr=0,totb=0,totg=0;
        for(int i=0;i<n;++i){
            string c;int x;
            cin>>c>>x;
            if(c[0]=='R') totr+=x;
            else if(c[0]=='B') totb+=x;
            else sum^=x;
        }
        if(sum) totb--;
        if(totr<=totb) cout<<"NO\n";
        else cout<<"YES\n";
    }
}

首先打个表找出所有的质数串，发现只有9个数，于是直接O(n)扫一遍就可以了
奈何我傻乎乎的开了个1e6的数组并且每次询问都memset一下，我不t谁t
接下来试了一下string的substr操作，发现也t，看来string的骚操作不能多用啊

#include<bits/stdc++.h>
using namespace std;
#define maxn (int(1e6)+100)
#define mod ((int)1e9+7)
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define lll lon long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define pb push_back
int main(){
    //s[0]="2";s[1]="3";s[2]="5";s[3]="7";s[4]="23";s[5]="37";s[6]="53";s[7]="73";s[8]="373";
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        string str;cin>>str;
        int ans=0;
        for(int i=0;i<n;++i){
            if(str[i]=='2'){
                ans++;
                if(i+1<n&&str[i+1]=='3') ans++;
            }
            else if(str[i]=='3'){
                ans++;
                if(i+1<n&&str[i+1]=='7'){
                    ans++;
                    if(i+2<n&&str[i+2]=='3') ans++;
                }
            }
            else if(str[i]=='5'){
                ans++;
                if(i+1<n&&str[i+1]=='3') ans++;
            }
            else if(str[i]=='7'){
                ans++;
                if(i+1<n&&str[i+1]=='3') ans++;
            }
        }
        cout<<ans<<endl;
    }
}

订阅评论
提醒
0 评论
内联反馈
查看所有评论