好。

我寻思着有几天没更新博客了

最近几场的cf,除了上次div3涨了一次rating

其他几场比赛都或多或少的掉了rating

(给你们一张图感受一下

然后paidy突然想打一场div2

然后就把大号给了paidy

自己拿小号去打了

A. Sea Battle

题意:

把两个矩形合起来,求外面绕一圈围住要多少格子

题解:

直接算就好

看代码的公式

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 4000005
#define int long long
#define ll long long
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,a[Max],n2,m2,ans;
signed main()
{
    n=read(),m=read(),n2=read(),m2=read();
    ans=n*2+m*2+n2*2+m2*2+8;
    ans-=2*(min(n,n2)+2);
    cout<<ans<<endl;
}

paidy代码:

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1;char cc=getchar();
    while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}
    while(cc>='0' && cc<='9') {x=x*10+cc-'0';cc=getchar();}
    return x*f;
}

int w1,h1,w2,h2;

int main(){
    w1=read();h1=read();w2=read();h2=read();
    printf("%d",2*w1+2*h1+4+2*w2+2*h2+4-w2-2-2-w2);
}

B. Draw!

题意:

假想你在看球赛

给定n个中间的比赛情况

求最多有多少次平局

(0,0)也算平局

题解:

细节题,样例给了等于没给

合并注意细节就好了

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 4000005
#define int long long
#define ll long long
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,a,b,c,d,ans=0;
signed main()
{
    n=read();
    c=0,d=0;
    ans++;
    for(int i=1;i<=n;i++)
    {
        a=read(),b=read();
        if(min(a,b)==min(c,d)&&max(a,b)==max(c,d)) continue;
        if(c==d) ans+=max(0ll,min(a,b)-max(c,d));
        if(c!=d) ans+=max(0ll,min(a,b)-max(c,d)+1);
        c=a,d=b;
    }
    cout<<ans<<endl;
}

paidy代码:

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1;char cc=getchar();
    while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}
    while(cc>='0' && cc<='9') {x=x*10+cc-'0';cc=getchar();}
    return x*f;
}

int n,ans,a,b;

int main(){
    n=read();ans=1;
    for(int i=1;i<=n;i++){
        int c=read();int d=read();
        if(a==c && b==d) continue;
        if(a==b) ans--;
        if(a<=b && b<=c && c<=d) ans+=c-b+1;
        else if(a<=b && b<=d && d<=c) ans+=d-b+1;
        else if(b<=a && a<=c && c<=d) ans+=c-a+1;
        else if(b<=a && a<=d && d<=c) ans+=d-a+1;
        a=c;b=d;
    }
    printf("%d",ans);
}

C. Birthday

题意:

构造一个n个点的环,相邻两个值的差的和最小

题解:

排序后跳着选就好了。

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 4000005
#define int long long
#define ll long long
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,a[Max],b[Max];
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+1+n);
    int j=0;
    for(int i=1;i<=n;i+=2) b[++j]=a[i];
    if(n&1) m=n-1;
    else m=n;
    for(int i=m;i>=2;i-=2) b[++j]=a[i];
    for(int i=1;i<=n;i++)
        printf("%lld ",b[i]);
}

paidy代码:

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1;char cc=getchar();
    while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}
    while(cc>='0' && cc<='9') {x=x*10+cc-'0';cc=getchar();}
    return x*f;
}

int n,a[110],ans,b,c;

int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i+=2) printf("%d ",a[i]);
    if(n&1) for(int i=n-1;i>0;i-=2) printf("%d ",a[i]);
    else for(int i=n;i>0;i-=2) printf("%d ",a[i]);
}

D. Gourmet choice

题意:

自己看题好了,懒得写了。

题解:

比赛中没打出来。

判无解比较麻烦。

判完后一个拓扑就好了。

paidy代码:

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1;char cc=getchar();
    while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}
    while(cc>='0' && cc<='9') {x=x*10+cc-'0';cc=getchar();}
    return x*f;
}

int n,m,l[2020][2020],d[2020],dui[2020],f[2020],ans[2020],v[2020];
char c[2020][2020];

inline int getfat(int k){
    if(f[k]==k) return k;
    f[k]=getfat(f[k]);
    return f[k];
}

int main(){
    n=read();m=read();
    for(int i=1;i<=n+m;i++) f[i]=i;
    for(int i=1;i<=n;i++){
        for(int j=n+1;j<=n+m;j++) c[i][j]=getchar();
        getchar();
    }
    for(int i=1;i<=n;i++){
        for(int j=n+1;j<=n+m;j++)if(c[i][j]=='='){
            getfat(i);getfat(j);
            if(f[i]==f[j]) continue;
            f[f[i]]=f[j];
        }
    }
    for(int i=1;i<=n+m;i++) getfat(i);
    for(int i=1;i<=n;i++){
        for(int j=n+1;j<=n+m;j++)if(c[i][j]!='=' && f[i]==f[j]){
            printf("No");return 0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=n+1;j<=n+m;j++)if(c[i][j]!='='){
            if(c[i][j]=='<'){
                if(l[f[j]][f[i]]){
                    printf("No");return 0;
                }
                if(!l[f[i]][f[j]]) d[f[j]]++;
                l[f[i]][f[j]]=1;
            }
            if(c[i][j]=='>'){
                if(l[f[i]][f[j]]){
                    printf("No");return 0;
                }
                if(!l[f[j]][f[i]]) d[f[i]]++;
                l[f[j]][f[i]]=1;
            }
        }
    }
    for(int i=1;i<=n+m;i++) if(f[i]!=i) v[i]=1;
    int t1=0;int t2=0;
    for(int i=1;i<=n+m;i++) if(!v[i] && d[i]==0){
        t2++;dui[t2]=i;ans[i]=1;
    }
    while(t1<t2){
        t1++;v[dui[t1]]=1;
        for(int i=1;i<=n+m;i++) if(l[dui[t1]][i]){
            d[i]--;ans[i]=max(ans[i],ans[dui[t1]]+1);
            if(d[i]==0){
                t2++;dui[t2]=i;
            }
        }
    }
    for(int i=1;i<=n+m;i++) if(!v[i]){
        printf("No"); return 0;
    }
    for(int i=1;i<=n+m;i++) if(f[i]!=i) ans[i]=ans[f[i]];
    printf("Yes\n");
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    printf("\n");
    for(int i=n+1;i<=n+m;i++) printf("%d ",ans[i]);
}

E. String Multiplication

题意:

规定了两个字符串的乘法

qwq*ab=abqabwabq

叫你求p_1*p_2*p_3*p_4*p_5*...*p_n的最长相同字符子串

比如aaabbvqwqwq的最长相同字符子串是aaa

题解:

这题大模拟

没打出来

paidy原话:

paidy:就是一堆讨论嘛

paidy:先取最后一个串的最长的

paidy:然后判最后一个串首尾相不相同

paidy:然后再一个一个往上判

我:这样啊

我:那不是傻逼大模拟吗

paidy:救世啊

paidy代码:

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;

inline int read(){
    int x=0,f=1;char cc=getchar();
    while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}
    while(cc>='0' && cc<='9') {x=x*10+cc-'0';cc=getchar();}
    return x*f;
}

int n,len[maxn],ans;
string s[maxn];
char x;

int main(){
    n=read();
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) len[i]=s[i].length();
    int tmp=0;ans=1;
    for(int i=1;i<len[n];i++){
        if(s[n][i]!=s[n][i-1]) tmp=i;
        ans=max(ans,i-tmp+1);
    }
    if(s[n][0]!=s[n][len[n]-1]){
        int tmp=1;
        for(int i=1;i<len[n];i++){
            if(s[n][i]!=s[n][i-1]) break;
            tmp++;
        }
        int flag=0;
        for(int i=1;i<n;i++)for(int j=0;j<len[i];j++) if(s[i][j]==s[n][0]) flag=1;
        ans=max(ans,tmp+flag);
        tmp=1;
        for(int i=len[n]-2;i>=0;i--){
            if(s[n][i]!=s[n][i+1]) break;
            tmp++;
        }
        for(int i=1;i<n;i++)for(int j=0;j<len[i];j++) if(s[i][j]==s[n][len[n]-1]) flag=1;
        ans=max(ans,tmp+flag);
        printf("%d",ans);
        return 0;
    }
    tmp=0;
    x=s[n][0];
    for(int k=n;k>=1;k--){
        int flag=1;
        for(int i=0;i<len[k];i++) if(s[k][i]!=x) flag=0;
        if(!flag){
            int l=0;int r=0;
            for(int i=0;i<len[k];i++){
                if(s[k][i]!=x) break;
                l++;
            }
            for(int i=len[k]-1;i>=0;i--){
                if(s[k][i]!=x) break;
                r++;
            }
            int t=0;
            for(int i=0;i<len[k];i++){
                t++;
                if(s[k][i]!=x) t=0;
                tmp=max(tmp,t);
            }
            int g=0;
            for(int i=1;i<k;i++) for(int j=0;j<len[i];j++) if(s[i][j]==x) g=1;
            if(g) tmp=max(tmp,l+r+1);
            for(int i=k+1;i<=n;i++) tmp+=len[i]*(tmp+1);
            break;
        }
    }
    if(tmp==0)for(int i=1;i<=n;i++) tmp+=len[i]*(tmp+1);
    ans=max(ans,tmp);
    printf("%d",ans);
}

F. Asya And Kittens

题意:

自己看题就好了。

题解:

傻逼题

过的比DE多

并查集乱搞就好了。

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 4000005
#define int long long
#define ll long long
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,nt[Max],f[Max],t[Max];
il int getf(int x)
{
    return f[x]==x?x:f[x]=getf(f[x]);
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) f[i]=i,t[i]=i;
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read(),fu=getf(u),fv=getf(v);
        f[fv]=fu;
        nt[fv]=t[fu];
        t[fu]=t[fv];
        m=t[fu];
    }
    for(int i=1;i<=n;i++,m=nt[m])
        printf("%lld ",m);
}

paidy代码:

#include <bits/stdc++.h>
#define maxn 150010
using namespace std;

inline int read(){
    int x=0,f=1;char cc=getchar();
    while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}
    while(cc>='0' && cc<='9') {x=x*10+cc-'0';cc=getchar();}
    return x*f;
}

int n,f[maxn],t[maxn],g[maxn],p;

inline int getfat(int k){
    if(f[k]==k) return k;
    f[k]=getfat(f[k]);
    return f[k];
}

int main(){
    n=read();
    for(int i=1;i<=n;i++) f[i]=i,t[i]=i;
    for(int i=2;i<=n;i++){
        int x=read();int y=read();
        getfat(x);getfat(y);
        g[f[y]]=t[f[x]];
        t[f[x]]=t[f[y]];
        f[f[y]]=f[x];
        if(i==n) p=t[f[x]];
    }
    for(int i=1;i<=n;i++){
        printf("%d ",p);
        p=g[p];
    }
}

G. Most Dangerous Shark

这什么牛逼题目,比赛没人过

总结

你们感受一下

第一个paidy

第二个我

第三个Fungigv

手速还是差了点

D题差一点就写完了。

qwq。