# 輔仁中學114學年度學科能力競賽資訊科校內初賽解答
# 初賽題目
https://drive.google.com/file/d/1Gc-kO_fPxCOVtjRkAvmt_cMr6iPsXm9N/view
# 校內初賽練習連結
https://codeforces.com/contestInvitation/464baa45ac0b1f2390b0a05fd29cd33c58386a7f
## problem A-Hello World
### 考點:基本輸入輸出
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
int t;
cin>>t;
while(t--){
cin>>s;
cout<<"Hello, "<<s<<endl;
}
}
```
## problem B-蛤?除法
### 考點:浮點數數以及小數點後的輸出控制
```cpp=
#include <bits/stdc++.h>
using namespace std;
//考浮點數
int main(){
long long int a,b;
cin>>a>>b;
cout<<fixed<<setprecision(5)<<(long double)a/b<<endl;
}
```
## problem C-破譯密碼
### 考點:字元運算
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
int n;
int x;
cin>>s>>x>>n;
for(int i=0;i<x;i++){
if(s[i]+n<32){
cout<<" ";
}
else if(s[i]+n>126){
cout<<"~";
}
else
cout<<(char)(s[i]+n);
if(s[i]-n<32){
cout<<" ";
}
else if(s[i]-n>126){
cout<<"~";
}
else
cout<<(char)(s[i]-n);
}
}
```
## problem D-色塊計算
### 考點:地迴、暴力
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector<int> appear(101,0);
vector<vector<bool>> visited(101,vector<bool>(101,false));
vector<vector<int>> mapp(101,vector<int>(101));
int now;
int n,m;
void ff(int x,int y){
if(x<0 or x>=n ){}
else if(y<0 or y>=m){}
else if(mapp[x][y]==now and !visited[x][y]){
visited[x][y]=true;
ff(x+1,y);
ff(x-1,y);
ff(x,y+1);
ff(x,y-1);
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mapp[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!visited[i][j]){
now=mapp[i][j];
ff(i,j);
appear[now]++;
}
}
}
for(int i=1;i<101;i++){
cout<<i<<" "<<appear[i]<<endl;
}
}
```
## problem E-環圖?
### 考點:樹、樹的搜尋、邏輯
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Jackis666 ios::sync_with_stdio(0); cin.tie(0)
vector<vector<int>> graph;
vector<bool> visited;
void dfs(int s){
visited[s]=true;
for(int e:graph[s]){
if(!visited[e]){
dfs(e);
}
}
}
signed main(){
Jackis666;
int n,m;
cin>>n>>m;
graph.resize(n + 1);
visited.resize(n + 1, false);
vector<int> cc(n+1,0);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
cc[a]++;
cc[b]++;
}
if(n!=m){
cout<<"No";
return 0;
}
for(int i=1;i<=n;i++){
if(cc[i]!=2){
cout<<"No";
return 0;
}
}
dfs(1);
for(int i=1;i<=n;i++){
if(!visited[i]){
cout<<"No";
return 0;
}
}
cout<<"Yes";
}
```
## problem F-象棋危機
### 考點:邏輯判斷、大型實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
/*K/k: 帥/將
A/a: 仕/士
E/e: 相/象
H/h: 馬/馬
R/r: 車/車
C/c: 炮/包
S/s: 兵/卒
#代表那格沒東西
*/
int dx_h[8] = {-2, -2, 2, 2, -1, 1, -1, 1};//馬方向
int dy_h[8] = {-1, 1, -1, 1, -2, -2, 2, 2};
int bx_h[8] = {-1, -1, 1, 1, 0, 0, 0, 0};//馬有沒有被檔
int by_h[8] = {0, 0, 0, 0, -1, -1, 1, 1};
bool inBoard(int x, int y) {
return x >= 0 && x < 10 && y >= 0 && y < 9;
}
int main(){
char who;
cin>>who;
string mp[10];
for(int i=0;i<10;i++){
cin>>mp[i];
}
char tar=(who=='A')?'k':'K';//king
char sold=(who=='A')?'S':'s';//兵
char horse=(who=='A')?'H':'h';//馬
char rook=(who=='A')?'R':'r';//車
char cannon=(who=='A')?'C':'c';//炮
int tx=0,ty=0;
for(int i=0;i<10;i++){
for(int j=0;j<9;j++){
if(mp[i][j]==tar){
tx=j;ty=i;
break;
}
}
}
//先找兵
int dir=(who=='A')?-1:1;
if(ty+dir>=0 and ty+dir<10 and mp[ty + dir][tx] == sold){
cout << (who == 'A' ? "A" : "B") << endl;
return 0;
}
if(tx-1>=0 and mp[ty][tx-1]==sold){
cout << (who == 'A' ? "A" : "B") << endl;
return 0;
}
if(tx+1<9 and mp[ty][tx+1]==sold){
cout << (who == 'A' ? "A" : "B") << endl;
return 0;
}
//判斷馬
for (int d = 0; d < 8; ++d) {
int nx = tx + dx_h[d], ny = ty + dy_h[d];
int bx = tx + bx_h[d], by = ty + by_h[d];
if (inBoard(ny, nx) && inBoard(by, bx)) {
if (mp[ny][nx] == horse && mp[by][bx] == '#') {
cout << (who == 'A' ? "A" : "B") << endl;
return 0;
}
}
}
//判斷車
for(int d=-1;d<=1;d+=2){
//垂直
for(int y=ty+d;y>=0 and y<10;y+=d){
if(mp[y][tx]=='#') continue;
if(mp[y][tx]==rook){
cout << (who == 'A' ? "A" : "B") << endl;
return 0;
}
break;
}
for(int x=tx+d;x>=0 and x<9;x+=d){
if(mp[ty][x]=='#') continue;
if(mp[ty][x]==rook){
cout << (who == 'A' ? "A" : "B") << endl;
return 0;
}
break;
}
}
//判斷炮
for(int d=-1;d<=1;d+=2){
int ok=0;
for(int y=ty+d;y>=0 and y<10;y+=d){
if(mp[y][tx]!='#') ok++;
if(mp[y][tx]==cannon and ok==2){
cout << (who == 'A' ? "A" : "B") << endl;
return 0;
}
if(ok>2) break;
}
ok=0;
for(int x=tx+d;x>=0 and x<9;x+=d){
if(mp[ty][x]!='#') ok++;
if(mp[ty][x]==cannon and ok==2){
cout << (who == 'A' ? "A" : "B") << endl;
return 0;
}
if(ok>2) break;
}
}
//最後
cout<<"C"<<endl;
}
```
## problem G-老師生氣了!
### 考點:動態規劃(dp)、二分搜尋
#### 以0為底
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
//¦Òdp
struct student{
int s,e;
int teacher;
};
bool cmp(student &a,student &b){
if(a.e == b.e) {
return a.teacher < b.teacher;
}
return a.e < b.e;
}
signed main(){
int n;
cin>>n;
vector<student> st(n);
for(int i=0;i<n;i++){
cin>>st[i].s>>st[i].e>>st[i].teacher;
}
sort(st.begin(),st.end(),cmp);
vector<int> dp(n,0);
vector<int> people(n,0);
dp[0]=st[0].teacher;
people[0]=1;
for(int i=1;i<n;i++){
int now=st[i].teacher;
int left=0;int right=i-1;
while(left<=right){
int mid=(left+right)/2;
if(st[mid].e<st[i].s){
left=mid+1;
}
else{
right=mid-1;
}
}
if(right>=0){
now+=dp[right];
if(now>dp[i-1]){
people[i]=people[right]+1;
dp[i]=now;
}
else if(now==dp[i-1]){
people[i]=min(people[i-1],people[right]+1);
dp[i]=now;
}
else{
dp[i]=dp[i-1];
people[i]=people[i-1];
}
}
else{//若找不到就比較前一個和址選這一個
if (st[i].teacher > dp[i - 1]) {
dp[i] = st[i].teacher;
people[i] = 1;
}
else if(st[i].teacher == dp[i - 1]) {
dp[i] = st[i].teacher;
people[i] = min(people[i - 1], 1LL);
}
else{
dp[i] = dp[i - 1];
people[i] = people[i - 1];
}
}
}
cout<<people[n-1]<<" "<<dp[n-1];
}
```
#### 以1為底
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct student{
int s,e;
int teacher;
};
bool cmp(student &a,student &b){
if(a.e == b.e) {
return a.teacher < b.teacher;
}
return a.e < b.e;
}
signed main(){
int n;
cin>>n;
vector<student> st(n+1);st[0].s=0;st[0].e=0;st[0].teacher=0;
for(int i=1;i<=n;i++){
cin>>st[i].s>>st[i].e>>st[i].teacher;
}
sort(st.begin(),st.end(),cmp);
vector<int> dp(n+1,0);
vector<int> people(n+1,0);
dp[1]=st[1].teacher;
people[1]=1;
for(int i=2;i<=n;i++){
int now=st[i].teacher;
int left=0;int right=i-1;
while(left<=right){
int mid=(left+right)/2;
if(st[mid].e<st[i].s){
left=mid+1;
}
else{
right=mid-1;
}
}
now+=dp[right];
if(now>dp[i-1]){
people[i]=people[right]+1;
dp[i]=now;
}
else if(now==dp[i-1]){
people[i]=min(people[i-1],people[right]+1);
dp[i]=now;
}
else{
dp[i]=dp[i-1];
people[i]=people[i-1];
}
}
cout<<people[n]<<" "<<dp[n];
}
```
## problem H-為甚麼玻璃要上色?
### 考點:前綴和、邏輯判斷
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
//Jackis666
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
vector<int>cnt(n+1,0),a(m);
for(int i=0;i<m;i++){
cin>>a[i];
cnt[a[i]]++;
}
vector<int>pre(n+2,0);
for(int i=n;i>0;i--){
pre[i]=cnt[i]+pre[i+1];
}
long long ans=0;
for(int i=1;i<n;i++){
int l=pre[i];//左邊顏色
int r=pre[n-i];//右邊顏色
int c=pre[max(i,n-i)];//全部同一個顏色
ans+=1LL*l*r-c;
}
cout<<ans<<endl;
}
}
```
Sign in with Wallet
Connect another wallet