2021 Jiangsu Collegiate Programming Contest部分题解

• 目录
• • A. Spring Couplets
  • C. Magical Rearrangement
  • I. Fake Walsh Transform
  • J. Anti-merge
  • K. Longest Continuous 1
• 结语

思路：模拟

#include
using namespace std;
typedef unsigned long long int ll;
typedef pair P;
const ll maxn=1e5+10;
ll tt;
ll n;
string s[maxn],t[maxn];
ll pan(ll x,ll y){
    if(x<=2&&x>=1&&y>=3&&y<=4)return 1;
    return 0;
}
int main(){
    cin>>tt;
    while(tt--){
        ll flag=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>s[i];
        }
        for(int i=1;i<=n;i++){
            cin>>t[i];
        }
        for(int i=1;i<=n;i++){
            ll ns=s[i].length();
            ll nt=t[i].length();
            ll idx=s[i][ns-1]-'0',idy=t[i][nt-1]-'0';
            if(idx>idy){
                swap(idx,idy);
            }
            if(!pan(idx,idy)){
                flag=1;
                break;
            }
        }
        ll ns=s[n].length();
        ll nt=t[n].length();
        ll x=s[n][ns-1]-'0',y=t[n][nt-1]-'0';
        if(x>=3&&x<=4&&y<=2&&y>=1){
 
        }else{
            flag=1;
        }
        if(flag){
            cout<<"NO"<
            cout<<"YES"< 
C. Magical Rearrangement 
思路：从小到大贪心，在贪心过程中，每次取一个数的时候判断即可，如果剩下的数字总数为sum,最大的数量为maxv
 
如果这个最大的数量就是拿的这个数，那么2*maxv-sum≥12∗maxv−sum≥1时，那就不行
如果这个最大数量不是拿的这个数，那么2*maxv-sum>12∗maxv−sum>1时，那就不行
 
#include
using namespace std;
typedef long long int ll;
typedef pair P;
const ll maxn=1e5+10;
ll t;
ll n;
ll a[maxn];
ll sum=0;

bool ok=1;
void f()
{
    ok=1;ll Max=0;
    for(int i=0; i<=9; i++)
    {
        Max=max(Max,a[i]);
    }
    ll k=sum-Max;
    if(k
        ok=0;
        return ;
    }


}
vector ans;
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        sum=0;
        for(int i=0; i<=9; i++)
        {
            scanf("%lld",&a[i]);
            sum+=a[i];
        }
        if(sum==1&&a[0]==1){
            printf("0n");
            continue;
        }
        f();
        if(ok==0)
        {
            printf("-1n");
            continue;
        }
        int pre=-1;
        ll fl=0;
        while(1)
        {

            if(sum==0)break;
            //cout<
                if(pre==i)continue;
                if(ans.size()==0)
                {
                    if(a[i]>0&&i!=0)
                    {
                        a[i]--,sum--;
                        f();
                        if(ok==0)
                        {
                            a[i]++,sum++;
                            continue;
                        }
                       // printf("%d",i);
                        pre=i;
                        flag=1;
                        ans.push_back(i);
                        break;
                    }

                }else
                    {
                        if(a[i]>0)
                        {
                            a[i]--;
                            sum--;
                            f();
                            if(ok==0)
                            {
                                a[i]++,sum++;
                                continue;
                            }
                            pre=i;
                            ans.push_back(i);
                            flag=1;
                           // printf("%d",i);
                            break;
                        }
                    }

            }
            if(!flag){
                fl=1;
                break;
            }
        }
        if(fl){
            printf("-1n");
            continue;
        }
        for(auto to:ans){
            printf("%lld",to);
        }
        printf("n");
        ans.clear();

    }
    return 0;
}
 
I. Fake Walsh Transform 
思路：
 
 
#include
using namespace std;
typedef long long int ll;
typedef pair P;
const ll maxn=1e5+10;
ll t;
ll n,m;
ll pan(ll x){
    ll sum=0;
    while(x){
        if(x&1)sum++;
        x>>=1;
    }
    return sum;
}
int main(){
    //cout<>t;
    while(t--){
        cin>>n>>m;
        ll id=pan(m);
        ll ans=1;
        for(int i=1;i<=n;i++){
            ans=ans*2;
        }
        if(id)ans--;
        if(n!=1)cout<
            if(m==0){
                cout<<"1"<
                cout<<"2"< 
J. Anti-merge 
思路：如果矩阵中不会出现合并现象，即没有相邻数字一样时，直接就输出0 00即可。
 如果矩阵中有合并现象，那么 标签种类一定最少一定是1 11，因为合并现象指挥发生在相邻且相同的数字之间，那么只需要给相同数字且相邻的贴上标签1 11，另一个不贴标签，就能区分开两种数字，使其不合并，所以标签种类最少是1 11，标签种类为1 11的情况下，就是二分图染色，把格点看成图中的点，相邻就是连边，那么直接跑二分图就行，对每一个部分染色后，看哪种颜色少，就把哪种存到答案中。
 
#include
using namespace std;
int n,m;
int a[505][505];
int dx[4]= {0,1,0,-1};
int dy[4]= {1,0,-1,0};
int color[505][505];
vector > ans[4];
int check(int x,int y){
    int f1=0,f2=0;
    if(y>1&&a[x][y]==a[x][y-1])f1=1;
    if(x>1&&a[x][y]==a[x-1][y])f2=1;
    return (f1|f2);
}
void dfs(int x,int y,int c){
    color[x][y]=c;
    ans[c].push_back({x,y});
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>n||nx<1||ny<1||ny>m||(a[x][y]!=a[nx][ny]))continue;
        if(color[nx][ny])continue;
        dfs(nx,ny,3-c);
    }
    return ;

}
int main()
{

    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    int types=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(check(i,j)){
                types=1;
                break;
            }
        }
        if(types){
            break;
        }
    }
    if(!types){
        printf("0 0");
    }else{
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                ans[1].clear();
                ans[2].clear();
                if(!color[i][j]){
                    dfs(i,j,1);
                }
                if(ans[1].size()>ans[2].size()){
                    for(int k=0;k
                        ans[0].push_back(ans[2][k]);
                    }
                }else{
                    for(int k=0;k
                        ans[0].push_back(ans[1][k]);
                    }
                }
            }
        }
        cout<
            cout< 
K. Longest Continuous 1 
思路：打表找规律
 代码：
 
#include
using namespace std;
typedef long long int ll;
typedef pair P;
const ll maxn=1e5+10;
ll t;
ll s[100000];
int main()
{
    s[0]=0;
    s[1]=2;
    ll i=2;
    while(s[i-1]<=1e9&&i<=1e5){
        ll m=(pow(2,i)-pow(2,i-1))*i;
        s[i]=s[i-1]+m;

        ++i;

    }
    
    cin>>t;
    while(t--){
        ll k;
        cin>>k;
        ll j=0;
        if(k==1){
            cout<<0< 
结语 
 
“遇事不决可问春风，春风不语即随本心”的意思是：对一件事犹豫不决，就问春风该如何做，春风给不出答案，就凭自己本心做出决断。“遇事不决可问春风，春风不语即随本心”一句出自网络作家“烽火戏诸侯”的《剑来》，其原文是：“遇事不决，可问春风。春风不语，遵循己心”。