跳转至

十六届 C++A 组暴力

第一题

寻找质数

5分 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool isprime(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0) return false;
    }
    return true;
}

int main(){
    int cnt=0;

    for(int i=2;;i++){
        if(isprime(i)) cnt++;
        if(cnt==2025){
            cout<<i;
            break;
        }
    }

    return 0;
}

import java.util.*;

public class Main {

    static boolean isprime(int x){
        for(int i=2;i*i<=x;i++){
            if(x%i==0) return false;
        }
        return true;
    }

    public static void main(String[] args){
        int cnt=0;

        for(int i=2;;i++){
            if(isprime(i)) cnt++;
            if(cnt==2025){
                System.out.println(i);
                break;
            }
        }
    }
}

def isprime(x):
    i=2
    while i*i<=x:
        if x%i==0:
            return False
        i+=1
    return True

cnt=0
i=2

while True:
    if isprime(i):
        cnt+=1
    if cnt==2025:
        print(i)
        break
    i+=1

第二题

黑白棋

5分 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[6][6]={
{1,0,-1,0,-1,-1},
{-1,-1,-1,0,-1,-1},
{-1,-1,-1,-1,0,0},
{-1,-1,-1,-1,-1,-1},
{-1,-1,1,-1,-1,1},
{-1,0,-1,-1,1,-1},
};

bool check(){
    for(int i=0;i<=5;i++){
        int ans1=0;
        for(int j=0;j<=5;j++){
            if(a[i][j]==0) ans1++;
        }
        if(ans1!=3) return false;
    }

    for(int i=0;i<=5;i++){
        int ans1=0;
        for(int j=0;j<=5;j++){
            if(a[j][i]==0) ans1++;
        }
        if(ans1!=3) return false;
    }

    for(int i=0;i<=5;i++){
        for(int j=1;j<=4;j++){
            if(a[i][j-1]==a[i][j] && a[i][j]==a[i][j+1]){
                return false;
            }
        }
    }

    for(int i=0;i<=5;i++){
        for(int j=1;j<=4;j++){
            if(a[j-1][i]==a[j][i] && a[j][i]==a[j+1][i]){
                return false;
            }
        }
    }

    set<int> s1,s2;

    for(int i=0;i<=5;i++){
        int res=0;
        for(int j=0;j<=5;j++){
            res=res*2+a[i][j];
        }
        if(s1.count(res)) return false;
        s1.insert(res);
    }

    for(int i=0;i<=5;i++){
        int res=0;
        for(int j=0;j<=5;j++){
            res=res*2+a[j][i];
        }
        if(s2.count(res)) return false;
        s2.insert(res);
    }

    return true;
}

void dfs(int x,int y){
    int nx=x,ny=y;

    if(ny==5){
        ny=0;
        nx++;
    }else{
        ny++;
    }

    if(x==6&&y==0){
        if(check()){
            for(int i=0;i<6;i++){
                for(int j=0;j<6;j++){
                    cout<<a[i][j];
                }
            }
            exit(0);
        }
        return;
    }

    if(a[x][y]!=-1){
        dfs(nx,ny);
        return;
    }

    a[x][y]=1;
    dfs(nx,ny);

    a[x][y]=0;
    dfs(nx,ny);

    a[x][y]=-1;
}

int main(){
    dfs(0,0);
    return 0;
}

import java.util.*;

public class Main {

    static int[][] a = {
        {1,0,-1,0,-1,-1},
        {-1,-1,-1,0,-1,-1},
        {-1,-1,-1,-1,0,0},
        {-1,-1,-1,-1,-1,-1},
        {-1,-1,1,-1,-1,1},
        {-1,0,-1,-1,1,-1},
    };

    static boolean check(){
        for(int i=0;i<6;i++){
            int cnt=0;
            for(int j=0;j<6;j++){
                if(a[i][j]==0) cnt++;
            }
            if(cnt!=3) return false;
        }

        for(int i=0;i<6;i++){
            int cnt=0;
            for(int j=0;j<6;j++){
                if(a[j][i]==0) cnt++;
            }
            if(cnt!=3) return false;
        }

        for(int i=0;i<6;i++){
            for(int j=1;j<=4;j++){
                if(a[i][j-1]==a[i][j] && a[i][j]==a[i][j+1]){
                    return false;
                }
            }
        }

        for(int i=0;i<6;i++){
            for(int j=1;j<=4;j++){
                if(a[j-1][i]==a[j][i] && a[j][i]==a[j+1][i]){
                    return false;
                }
            }
        }

        HashSet<Integer> s1=new HashSet<>();
        HashSet<Integer> s2=new HashSet<>();

        for(int i=0;i<6;i++){
            int res=0;
            for(int j=0;j<6;j++){
                res=res*2+a[i][j];
            }
            if(s1.contains(res)) return false;
            s1.add(res);
        }

        for(int i=0;i<6;i++){
            int res=0;
            for(int j=0;j<6;j++){
                res=res*2+a[j][i];
            }
            if(s2.contains(res)) return false;
            s2.add(res);
        }

        return true;
    }

    static void dfs(int x,int y){
        int nx=x,ny=y;

        if(ny==5){
            ny=0;
            nx++;
        }else{
            ny++;
        }

        if(x==6 && y==0){
            if(check()){
                for(int i=0;i<6;i++){
                    for(int j=0;j<6;j++){
                        System.out.print(a[i][j]);
                    }
                }
                System.exit(0);
            }
            return;
        }

        if(a[x][y]!=-1){
            dfs(nx,ny);
            return;
        }

        a[x][y]=1;
        dfs(nx,ny);

        a[x][y]=0;
        dfs(nx,ny);

        a[x][y]=-1;
    }

    public static void main(String[] args){
        dfs(0,0);
    }
}

import sys
sys.setrecursionlimit(10**7)

a = [
    [1,0,-1,0,-1,-1],
    [-1,-1,-1,0,-1,-1],
    [-1,-1,-1,-1,0,0],
    [-1,-1,-1,-1,-1,-1],
    [-1,-1,1,-1,-1,1],
    [-1,0,-1,-1,1,-1],
]

def check():
    for i in range(6):
        if sum(1 for j in range(6) if a[i][j]==0) != 3:
            return False

    for i in range(6):
        if sum(1 for j in range(6) if a[j][i]==0) != 3:
            return False

    for i in range(6):
        for j in range(1,5):
            if a[i][j-1]==a[i][j]==a[i][j+1]:
                return False

    for i in range(6):
        for j in range(1,5):
            if a[j-1][i]==a[j][i]==a[j+1][i]:
                return False

    s1=set()
    s2=set()

    for i in range(6):
        res=0
        for j in range(6):
            res=res*2+a[i][j]
        if res in s1:
            return False
        s1.add(res)

    for i in range(6):
        res=0
        for j in range(6):
            res=res*2+a[j][i]
        if res in s2:
            return False
        s2.add(res)

    return True

def dfs(x,y):
    if y==5:
        nx,ny=x+1,0
    else:
        nx,ny=x,y+1

    if x==6 and y==0:
        if check():
            for i in range(6):
                for j in range(6):
                    print(a[i][j],end="")
            sys.exit(0)
        return

    if a[x][y]!=-1:
        dfs(nx,ny)
        return

    a[x][y]=1
    dfs(nx,ny)

    a[x][y]=0
    dfs(nx,ny)

    a[x][y]=-1

dfs(0,0)

第三题

抽奖

10分 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e3+10;

int a[N],b[N],c[N];

int calc(int x,int y,int z){
    vector<int> v;
    v.push_back(x);
    v.push_back(y);
    v.push_back(z);

    if(v[0]+1==v[1] && v[1]+1==v[2]) return 200;

    sort(v.begin(),v.end());

    if(v[0]==v[1] && v[1]==v[2]) return 200;
    if(v[0]+1==v[1] && v[1]+1==v[2]) return 100;
    if(v[0]==v[1] || v[1]==v[2]) return 100;

    return 0;
}

int main(){
    int n;
    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>c[i];

    int m;
    cin>>m;

    int x=1,y=1,z=1;
    int ans=0;

    while(m--){
        int x1,x2,x3;
        cin>>x1>>x2>>x3;

        x=(x+x1)%n;
        y=(y+x2)%n;
        z=(z+x3)%n;

        if(x==0) x=n;
        if(y==0) y=n;
        if(z==0) z=n;

        ans+=calc(a[x],b[y],c[z]);
    }

    cout<<ans;

    return 0;
}

import java.util.*;

public class Main {

    static final int N=1010;
    static int[] a=new int[N];
    static int[] b=new int[N];
    static int[] c=new int[N];

    static int calc(int x,int y,int z){
        int[] v={x,y,z};

        if(v[0]+1==v[1] && v[1]+1==v[2]) return 200;

        Arrays.sort(v);

        if(v[0]==v[1] && v[1]==v[2]) return 200;
        if(v[0]+1==v[1] && v[1]+1==v[2]) return 100;
        if(v[0]==v[1] || v[1]==v[2]) return 100;

        return 0;
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);

        int n=sc.nextInt();

        for(int i=1;i<=n;i++) a[i]=sc.nextInt();
        for(int i=1;i<=n;i++) b[i]=sc.nextInt();
        for(int i=1;i<=n;i++) c[i]=sc.nextInt();

        int m=sc.nextInt();

        int x=1,y=1,z=1;
        int ans=0;

        while(m-->0){
            int x1=sc.nextInt();
            int x2=sc.nextInt();
            int x3=sc.nextInt();

            x=(x+x1)%n;
            y=(y+x2)%n;
            z=(z+x3)%n;

            if(x==0) x=n;
            if(y==0) y=n;
            if(z==0) z=n;

            ans+=calc(a[x],b[y],c[z]);
        }

        System.out.println(ans);
    }
}

n=int(input())

a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
c=[0]+list(map(int,input().split()))

def calc(x,y,z):
    v=[x,y,z]

    if v[0]+1==v[1] and v[1]+1==v[2]:
        return 200

    v.sort()

    if v[0]==v[1]==v[2]:
        return 200
    if v[0]+1==v[1] and v[1]+1==v[2]:
        return 100
    if v[0]==v[1] or v[1]==v[2]:
        return 100

    return 0

m=int(input())

x=y=z=1
ans=0

for _ in range(m):
    x1,x2,x3=map(int,input().split())

    x=(x+x1)%n
    y=(y+x2)%n
    z=(z+x3)%n

    if x==0: x=n
    if y==0: y=n
    if z==0: z=n

    ans+=calc(a[x],b[y],c[z])

print(ans)

第四题

红黑树

8分 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+10;

int a[N];

void dfs(int id,int color){
    if(id>1000000) return;

    a[id]=color;

    if(color==1){
        dfs(id*2,1);
        dfs(id*2+1,0);
    }else{
        dfs(id*2,0);
        dfs(id*2+1,1);
    }
}

int main(){
    dfs(1,1);

    int n,m,k;
    cin>>m;

    while(m--){
        cin>>n>>k;

        if(a[(1<<(n-1))-1+k]==1) cout<<"RED\n";
        else cout<<"BLACK\n";
    }

    return 0;
}

import java.util.*;

public class Main {

    static final int N=1000000+10;
    static int[] a=new int[N];

    static void dfs(int id,int color){
        if(id>1000000) return;

        a[id]=color;

        if(color==1){
            dfs(id*2,1);
            dfs(id*2+1,0);
        }else{
            dfs(id*2,0);
            dfs(id*2+1,1);
        }
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);

        dfs(1,1);

        int m=sc.nextInt();

        while(m-->0){
            int n=sc.nextInt();
            int k=sc.nextInt();

            if(a[(1<<(n-1))-1+k]==1) System.out.println("RED");
            else System.out.println("BLACK");
        }
    }
}

import sys
sys.setrecursionlimit(10**7)

N=10**6+10
a=[0]*N

def dfs(id,color):
    if id>1000000:
        return

    a[id]=color

    if color==1:
        dfs(id*2,1)
        dfs(id*2+1,0)
    else:
        dfs(id*2,0)
        dfs(id*2+1,1)

dfs(1,1)

m=int(input())

for _ in range(m):
    n,k=map(int,input().split())

    if a[(1<<(n-1))-1+k]==1:
        print("RED")
    else:
        print("BLACK")
10分 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int dfs(int n,int k){
    if(n==1 && k==1){
        return 1;
    }

    if(k%2==1){
        return dfs(n-1,k/2+1);
    }else{
        return 1-dfs(n-1,k/2);
    }
}

int main(){
    int m;
    cin>>m;

    while(m--){
        int n,k;
        cin>>n>>k;

        if(dfs(n,k)) cout<<"RED\n";
        else cout<<"BLACK\n";
    }

    return 0;
}

import java.util.*;

public class Main {

    static int dfs(int n,int k){
        if(n==1 && k==1){
            return 1;
        }

        if(k%2==1){
            return dfs(n-1,k/2+1);
        }else{
            return 1-dfs(n-1,k/2);
        }
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);

        int m=sc.nextInt();

        while(m-->0){
            int n=sc.nextInt();
            int k=sc.nextInt();

            if(dfs(n,k)==1) System.out.println("RED");
            else System.out.println("BLACK");
        }
    }
}

import sys
sys.setrecursionlimit(10**7)

def dfs(n,k):
    if n==1 and k==1:
        return 1

    if k%2==1:
        return dfs(n-1,k//2+1)
    else:
        return 1-dfs(n-1,k//2)

m=int(input())

for _ in range(m):
    n,k=map(int,input().split())

    if dfs(n,k):
        print("RED")
    else:
        print("BLACK")

第五题

黑客

5.25分 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5e5+10;

bool st[N];
int path[N];
int a[N];
int len;

set<vector<int>> s;

void dfs(int u){
    if(u==len+1){
        int n=path[1],m=path[2];
        if(n*m!=len-2) return;

        vector<int> v;
        for(int i=1;i<=len;i++) v.push_back(path[i]);

        s.insert(v);
        return;
    }

    for(int i=1;i<=len;i++){
        if(st[i]) continue;

        st[i]=true;
        path[u]=a[i];

        dfs(u+1);

        st[i]=false;
    }
}

int main(){
    cin>>len;

    for(int i=1;i<=len;i++) cin>>a[i];

    dfs(1);

    cout<<s.size();

    return 0;
}

import java.util.*;

public class Main {

    static int N=500010;

    static boolean[] st=new boolean[N];
    static int[] path=new int[N];
    static int[] a=new int[N];

    static int len;

    static HashSet<List<Integer>> s=new HashSet<>();

    static void dfs(int u){
        if(u==len+1){
            int n=path[1],m=path[2];
            if(n*m!=len-2) return;

            ArrayList<Integer> v=new ArrayList<>();
            for(int i=1;i<=len;i++) v.add(path[i]);

            s.add(v);
            return;
        }

        for(int i=1;i<=len;i++){
            if(st[i]) continue;

            st[i]=true;
            path[u]=a[i];

            dfs(u+1);

            st[i]=false;
        }
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);

        len=sc.nextInt();

        for(int i=1;i<=len;i++) a[i]=sc.nextInt();

        dfs(1);

        System.out.println(s.size());
    }
}

import sys
sys.setrecursionlimit(10**7)

len_n=int(input())
a=[0]+list(map(int,input().split()))

st=[False]*(len_n+1)
path=[0]*(len_n+1)

s=set()

def dfs(u):
    if u==len_n+1:
        n=path[1]
        m=path[2]
        if n*m!=len_n-2:
            return
        s.add(tuple(path[1:len_n+1]))
        return

    for i in range(1,len_n+1):
        if st[i]:
            continue

        st[i]=True
        path[u]=a[i]

        dfs(u+1)

        st[i]=False

dfs(1)

print(len(s))

第六题（官方数据偏弱）

好串的数目

15分（不水 12 分） 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    string s;
    cin>>s;

    int n=s.size();
    ll ans=0;

    for(int i=0;i<n;i++){
        int pre=-1;
        int cnt=0;

        for(int j=i;j<n;j++){
            if(pre==-1){
                ans++;
                pre=s[j];
                continue;
            }

            if(s[j]==pre || s[j]==pre+1){
                ans++;
                pre=s[j];
                continue;
            }

            cnt++;
            if(cnt==2){
                break;
            }

            ans++;
            pre=s[j];
        }
    }

    cout<<ans;

    return 0;
}

import java.util.*;

public class Main {

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);

        String s=sc.next();
        int n=s.length();

        long ans=0;

        for(int i=0;i<n;i++){
            int pre=-1;
            int cnt=0;

            for(int j=i;j<n;j++){
                if(pre==-1){
                    ans++;
                    pre=s.charAt(j);
                    continue;
                }

                if(s.charAt(j)==pre || s.charAt(j)==pre+1){
                    ans++;
                    pre=s.charAt(j);
                    continue;
                }

                cnt++;
                if(cnt==2){
                    break;
                }

                ans++;
                pre=s.charAt(j);
            }
        }

        System.out.println(ans);
    }
}

s=input()
n=len(s)

ans=0

for i in range(n):
    pre=-1
    cnt=0

    for j in range(i,n):
        if pre==-1:
            ans+=1
            pre=ord(s[j])
            continue

        if ord(s[j])==pre or ord(s[j])==pre+1:
            ans+=1
            pre=ord(s[j])
            continue

        cnt+=1
        if cnt==2:
            break

        ans+=1
        pre=ord(s[j])

print(ans)