第九届编程大赛预选赛

• 有些题目可能有c++版本和py版本

https://www.xujcoj.com/home/problem/detail/3617

#include
using namespace std;
//也可以用sort()函数
int main(){
    int m;
    cin>>m;
    sets;
    getchar();//清除m的换行符
    while(m--){
        string x;
        getline(cin,x);
        s.insert(x);//set自动排序
    }
    for(auto it:s){
        printf("%s YYDS!n",it.c_str());
    }
}

a=list()
m=eval(input())
while m:
    m-=1
    s=input()
    a.append(s)
a.sort()
for i in a:
    print('{} YYDS!'.format(i))

https://www.xujcoj.com/home/problem/detail/3618

#include
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int m;
        cin>>m;
        int a[m];
        int sum=0;
        for(int j=0;j>a[j];
            sum+=a[j];
        }//一定要读完
        int cnt=0;
        for(int j=0;j=85)
                cnt++;
        }
        if(cnt==m&&sum>=90*m)//除法可能有精度问题
            printf("No.%d TQLn",i);
    }
}

n = eval(input())
for i in range(1, n + 1):
    score = list(map(int, input().split()))
    m = score[0]
    score.remove(m)
    _sum = sum(score)
    cnt = 0
    for j in score:
        if j < 60:
            print('No.{} TCL'.format(i))
            break
        if j >= 85:
            cnt += 1
    if cnt == m and _sum >= 90 * m:
        print('No.{} TQL'.format(i))

https://www.xujcoj.com/home/contest/1098/problem/3

前缀和

#include
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int d[maxn][11];//前缀和数组，第一个代表学生序号，第二个1-9代表各科成绩，10代表总成绩
int main() {
    int m;
    scanf("%d",&m);//此题cin和scanf差的时间很大，所以用scanf
    for (int i = 1; i <= m; ++i) {
        int sum=0;
        for(int j=1;j<=9;++j){
            int x;
            scanf("%d",&x);//直接读入数据不增开数组，增开会导致内存溢出
            sum+=x;
            d[i][j]=d[i-1][j]+x;
        }
        d[i][10]=d[i-1][10]+sum;
    }
    int q;//开始查询
    scanf("%d",&q);
    while(q--){
        int a,b;
        string c;
        scanf("%d %d",&a,&b);
        cin>>c;//我不会用scanf读字符串
        if(c=="ALL"){
            cout<<(d[b][10]-d[a-1][10])/(b-a+1)< 
四、回文姓名 
题目链接： 
https://www.xujcoj.com/home/problem/detail/3620
 
c++_code: 
#include
using namespace std;
typedef long long ll;
//这题应该有很多想法，我的想法是找到韵母前的声母位置，要特判o和h，因为ou可以成为一个拼音，h前还能跟z、c、s，然后进行对比
int main() {
    int m;
    cin >> m;
    while (m--) {
        string xing, ming;
        cin >> xing >> ming;
        int pos = 0;
        bool f = 0;
        for (int i = 2; i < ming.size(); ++i) {
            if (ming[i] == 'a' || ming[i] == 'e' || ming[i] == 'i' || ming[i] == 'o' || ming[i] == 'u') {
                if (ming[i] == 'o') {
                    if (ming[i - 1] == 'a' || ming[i - 1] == 'e' || ming[i - 1] == 'i' || ming[i - 1] == 'o' ||ming[i - 1] == 'u') {
                        pos = i;
                        f++;
                    }
                    else if (ming[i - 1] != 'a' && ming[i - 1] != 'e' && ming[i - 1] != 'i' && ming[i - 1] != 'o' &&ming[i - 1] != 'u') {
                        if (ming[i - 1] == 'h') {
                            if (ming[i - 2] == 'z' || ming[i - 2] == 'c' || ming[i - 2] == 's') {
                                pos = i - 2;
                                f++;
                            }
                            else {
                                pos = i - 1;
                                f++;
                            }
                        }
                        else {
                            pos = i - 1;
                            f++;
                        }
                    }
                }
                else {
                    if (ming[i - 1] != 'a' && ming[i - 1] != 'e' && ming[i - 1] != 'i' && ming[i - 1] != 'o' &&ming[i - 1] != 'u') {
                        if (ming[i - 1] == 'h') {
                            if (ming[i - 2] == 'z' || ming[i - 2] == 'c' || ming[i - 2] == 's') {
                                pos = i - 2;
                                f++;
                            }
                            else {
                                pos = i - 1;
                                f++;
                            }
                        }
                        else{
                            pos=i-1;
                            f++;
                        }
                    }
                }
            }
        }
        string ans;
        ans = pos == 1 ? ming : ming.substr(pos);
        if (ans[0] >= 'a' && ans[0] <= 'z')
            ans[0] = char(ans[0] - 32);
        //cout << ans << endl;
        if(ans==xing)puts("Yes");
        else puts("No");
    }
}
 
五、孤独的岛屿 
题目链接： 
https://www.xujcoj.com/home/problem/detail/3622
 
算法： 
并查集
 
c++_code: 
#include
using namespace std;
typedef long long ll;
int pre[114];
int find(int x){//找到根节点
    return x==pre[x]?x:find(pre[x]);
}
int main() {
    int n;
    cin >> n;
    while (n--) {
        int m, p;
        cin >> m >> p;
        for (int i = 1; i <= m; i++) {
            pre[i] = i;//所有岛屿都还没连接
        }
        while (p--) {
            int a, b;
            cin >> a >> b;
            int x = find(a);
            int y = find(b);
            if (x != y) pre[x] = pre[y];//如果没有间接连接，就连接
        }
        set ans;
        for (int j = 1; j <= m; j++) {
            ans.insert(find(j));//set存不同的根节点
        }
        cout<<((ans.size()==1)?0:ans.size())< 
python_code: 
pre=[0 for x in range(114) ]


def find(x):
    if x==pre[x]:
        return x
    else:
        return find(pre[x])

    
n=eval(input())
while n:
    n-=1
    k = [0 for x in range(114)]
    m,p=map(int,input().split())
    for i in range(1,m+1):
        pre[i]=i
    while p:
        p-=1
        a,b=map(int,input().split())
        x=find(a)
        y=find(b)
        if x!=y:
            pre[x]=pre[y]
    for i in range(1,m+1):
        k[find(i)]=1
    ans=0
    for i in range(1,m+1):
        if k[i]:
            ans+=1
    if ans==1:
        ans=0
    print(ans)


 
六、牧夫座空洞 
题目链接： 
https://www.xujcoj.com/home/problem/detail/3624
 
算法： 
BFS、DFS
 
DFS_code: 
#include
using namespace std;
typedef long long ll;
ll T,a,b,c;
int book[14][14][14];
ll dir[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
ll dfs(int x,int y,int z)
{
    if(book[x][y][z])return 0;
    ll tx,ty,tz,ans=1;
    book[x][y][z]=1;
    for(ll i=0;i<6;i++)
    {
        tx=x+dir[i][0];
        ty=y+dir[i][1];
        tz=z+dir[i][2];
        ans+=dfs(tx,ty,tz);
    }
    return ans;
}
int main() {
    int n;
    cin>>n;
    while(n--){
        int a,b,c;
        cin>>a>>b>>c;
        memset(book,1,sizeof(book));//初始化
        for (int i = 1; i <= a; ++i) {//输入
            for (int j = 1; j <= b; ++j) {
                for (int k = 1; k <= c; ++k) {
                    cin>>book[i][j][k];
                }
            }
        }
        ll ans=1;
        for (int i = 1; i <= a; ++i) {//搜索
            for (int j = 1; j <= b; ++j) {
                for (int k = 1; k <= c; ++k) {
                        if(!book[i][j][k])
                            ans=max(ans,dfs(i,j,k));
                }
            }
        }
        cout<
 
BFS_code: 
#include
using namespace std;
typedef long long ll;
int h[14][14][14];
int x,y,z;
int dir[6][3]{1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
struct hole{
    int x,y,z;
};
int bfs(int a,int b,int c){//标准模板
    int ans=1;
    queueq;
    h[a][b][c]=1;
    q.push({a,b,c});
    while(q.size()){
        hole now=q.front();
        q.pop();
        hole next;
        for (int i = 0; i <6 ; ++i) {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            next.z=now.z+dir[i][2];
            if(next.x>=1&&next.x<=x&&next.y>=1&&next.y<=y&&next.z>=1&&next.z<=z) {
                if(!h[next.x][next.y][next.z]){
                    ans++;
                    q.push(next);
                    h[next.x][next.y][next.z]=1;
                }
            }
        }
    }
    return ans;
}
int main(){
    int n;
    cin>>n;
    while(n--){
       memset(h,1,sizeof(h));//初始化
        cin>>x>>y>>z;
        for (int i = 1; i <=x; ++i) {//输入
            for (int j = 1; j <=y ; ++j) {
                for (int k = 1; k <=z ; ++k) {
                    cin>>h[i][j][k];
                }
            }
        }
        int ans=0;
        for (int i = 1; i <=x; ++i) {//搜索
            for (int j = 1; j <=y ; ++j) {
                for (int k = 1; k <=z ; ++k) {
                    if(!h[i][j][k])
                        ans=max(ans,bfs(i,j,k));
                }
            }
        }
        cout<
 
七、数列-9 
题目链接： 
https://www.xujcoj.com/home/problem/detail/3621
 
算法： 
矩阵快速幂
 
c++_code: 
#include
using namespace std;
typedef long long ll;
const int mod=100000007;
ll t[10][10];
void multi(ll a[10][10],ll b[10][10]){//矩阵的乘法
    fill((ll*)t,(ll*)t+10*10,0);
    for (int i=0; i<10; i++){
        for (int j = 0; j < 10; ++j) {
            for (int k = 0; k < 10;++k){
                t[i][j]=(t[i][j]+a[i][k]*b[k][j])%mod;
            }
        }
    }
    for (int i=0; i<10; ++i){
        for (int j = 0; j < 10; ++j){
            a[i][j]=t[i][j];
        }
    }
}
ll r[10][10];
void qp(ll a[10][10],int n){//矩阵快速幂（类似数乘的快速幂）
    fill((ll*)r,(ll*)r+10*10,0);
    for (int i = 0; i < 10; ++i) {
        r[i][i]=1;
    }
    while(n){
        if(n&1) multi(r,a);
        multi(a,a);
        n>>=1;
    }
}
int main() {
    int n;
    cin>>n;
    while(n--){
        //矩阵A(1,2,3,4，5,6,7,8,9,10)
        //AXB=(2,3,4,5,6,7,8,9,10,1*1+2*2+……+10*10)
        //所以AXB的最后一项就是得到的结果
        //线代好高深，我好菜！！！
        //观察得A*B^2就是第12项；
        //所以 第n项就是A*B^(n-10)的最后一项
        ll b[10][10]={
                {0,0,0,0,0,0,0,0,0,1},
                {1,0,0,0,0,0,0,0,0,2},
                {0,1,0,0,0,0,0,0,0,3},
                {0,0,1,0,0,0,0,0,0,4},
                {0,0,0,1,0,0,0,0,0,5},
                {0,0,0,0,1,0,0,0,0,6},
                {0,0,0,0,0,1,0,0,0,7},
                {0,0,0,0,0,0,1,0,0,8},
                {0,0,0,0,0,0,0,1,0,9},
                {0,0,0,0,0,0,0,0,1,10},
        };
        ll a[10],m;
        for (int i = 0; i < 10; ++i) {
            cin>>a[i];
        }
        cin>>m;
        if(m<=10)cout<