第九届编程大赛预选赛
- 有些题目可能有c++版本和py版本
一、YYDS
题目链接：
https://www.xujcoj.com/home/problem/detail/3617
c++_code:
#include<bits/stdc++.h>
using namespace std;
//也可以用sort()函数
int main(){
int m;
cin>>m;
set<string>s;
getchar();//清除m的换行符
while(m--){
string x;
getline(cin,x);
s.insert(x);//set自动排序
}
for(auto it:s){
printf("%s YYDS!\n",it.c_str());
}
}
python_code：
a=list()
m=eval(input())
while m:
m-=1
s=input()
a.append(s)
a.sort()
for i in a:
print('{} YYDS!'.format(i))
二、TCL和TQL
题目链接：
https://www.xujcoj.com/home/problem/detail/3618
c++_code:
#include<bits/stdc++.h>
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<m;j++){
cin>>a[j];
sum+=a[j];
}//一定要读完
int cnt=0;
for(int j=0;j<m;j++){
if(a[j]<60){
printf("No.%d TCL\n",i);
break;
}
if(a[j]>=85)
cnt++;
}
if(cnt==m&&sum>=90*m)//除法可能有精度问题
printf("No.%d TQL\n",i);
}
}
python_code:
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
算法：
前缀和
c++_code:
#include<bits/stdc++.h>
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)<<endl;
}
else{
int x=c[1]-'0';
cout<<(d[b][x]-d[a-1][x])/(b-a+1)<<endl;
}
}
}
四、回文姓名
题目链接：
https://www.xujcoj.com/home/problem/detail/3620
c++_code:
#include<bits/stdc++.h>
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<bits/stdc++.h>
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<int> ans;
for (int j = 1; j <= m; j++) {
ans.insert(find(j));//set存不同的根节点
}
cout<<((ans.size()==1)?0:ans.size())<<endl;
}
}
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<bits/stdc++.h>
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<<ans<<endl;
}
}
BFS_code:
#include<bits/stdc++.h>
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;
queue<hole>q;
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<<ans<<endl;
}
}
七、数列-9
题目链接：
https://www.xujcoj.com/home/problem/detail/3621
算法：
矩阵快速幂
c++_code:
#include<bits/stdc++.h>
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<<a[m-1]<<endl;//项数小于10直接输出，不用乘
else{
qp(b,m-10);
ll ans=0;
for (int i = 0; i < 10; ++i) {
ans=(ans+a[i]*r[i][9])%mod;//最后一次运算要自己写因为不是幂运算
}
cout<<ans<<endl;
}
}
}
