2020 SWJTU-ICPC Training Round #1 题解
双手敲尽代码也敲尽岁月 / 只有我一人 写的题解 / 凋零在OJ里面
A.Apples and Ideas
"If you have an apple and I have an apple and we exchange these apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas." - George Bernard Shaw
Now Alice has A apples and B ideas, while Bob has C apples and D ideas, what will they have if they exchange all things?
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The only line contains four integers A, B, C, D (0 <= A, B, C, D <= 100) - as the problem described.
Output
For each test case, output two lines. First line contains two integers, indicating the number of Alice's apples and ideas; second line contains two integers, indicating the number of Bob's apples and ideas.
Sample Input
4
0 0 5 30
20 25 20 0
20 25 20 15
20 25 25 30
Sample Output
5 30
0 30
20 25
20 25
20 40
20 40
25 55
20 55
思路
水题，区分苹果和思维，苹果只能交换，而主意交换只能是不变或是变多。
输入 A B C D 输出 C B+D A B+D 即可
代码
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int a,b,c,d;cin>>a>>b>>c>>d;
cout<<c<<" "<<b+d<<endl<<a<<" "<<b+d<<endl;
}
return 0;
}
C.Defuse the Bomb
The bomb is about to explode! Please defuse it as soon as possible!
There is a display showing a number from 1 to 4 on the bomb. Besides this, there are 4 buttons under the display. Each button is labeled by a number from 1 to 4. The numbers on the buttons are always distinct.
There are 5 defusing stages in total. Pressing the correct button can progress the bomb to the next defusing stage. The number on the display and the number on each button may be different in different stages. The bomb will be defused only when all 5 defusing stages get passed. Pressing the incorrect button will cause the bomb to explode immediately. Be careful!
Here is the detailed bomb defusing manual. Button positions are ordered from left to right.
Stage 1:
If the display is 1, press the button in the second position.
If the display is 2, press the button in the second position.
If the display is 3, press the button in the third position.
If the display is 4, press the button in the fourth position.
Stage 2:
If the display is 1, press the button labeled "4".
If the display is 2, press the button in the same position as you pressed in stage 1.
If the display is 3, press the button in the first position.
If the display is 4, press the button in the same position as you pressed in stage 1.
Stage 3:
If the display is 1, press the button with the same label you pressed in stage 2.
If the display is 2, press the button with the same label you pressed in stage 1.
If the display is 3, press the button in the third position.
If the display is 4, press the button labeled "4".
Stage 4:
If the display is 1, press the button in the same position as you pressed in stage 1.
If the display is 2, press the button in the first position.
If the display is 3, press the button in the same position as you pressed in stage 2.
If the display is 4, press the button in the same position as you pressed in stage 2.
Stage 5:
If the display is 1, press the button with the same label you pressed in stage 1.
If the display is 2, press the button with the same label you pressed in stage 2.
If the display is 3, press the button with the same label you pressed in stage 4.
If the display is 4, press the button with the same label you pressed in stage 3.
Input
There are multiple test cases. The first line of input is an integer T indicating the number of test cases. For each test case:
There are 5 lines. Each line contains 5 integers D, B1, B2, B3, B4 indicating the number on the display and the numbers on the buttons respectively. The i-th line correspond to the i-th stage.
Output
For each test case, output 5 lines. The i-th line contains two integers indicating the position and the label of the correct button for the i-th stage.
Sample Input
1
4 2 1 3 4
2 2 4 3 1
4 3 1 4 2
4 3 4 2 1
2 3 1 2 4
Sample Output
4 4
4 1
3 4
4 1
2 1
思路
按照题目要求一步步模拟就好了，注意和之前相同位置和相同标签是两回事
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int now[6];
int bj4[6];
int a[6][6],p[6],bq[6];
for(int i=1;i<=5;i++){
cin>>now[i];
for(int j=1;j<=4;j++){
cin>>a[i][j];
if(a[i][j]==4){
bj4[i]=j;
}
}
}
for(int i=1;i<=5;i++){
if(i==1){
if(now[i]==1){
cout<<"2 "<<a[i][2]<<endl;
p[1]=2;bq[1]=a[i][2];
}
else if(now[i]==2){
cout<<"2 "<<a[i][2]<<endl;
p[1]=2;bq[1]=a[i][2];
}
else if(now[i]==3){
cout<<"3 "<<a[i][3]<<endl;
p[1]=3;bq[1]=a[i][3];
}
else if(now[i]==4){
cout<<"4 "<<a[i][4]<<endl;
p[1]=4; bq[1]=a[i][4];
}
}
else if(i==2){
if(now[i]==1){
cout<<bj4[i]<<" 4"<<endl;
p[2]=bj4[i]; bq[2]=4;
}
else if(now[i]==2){
cout<<p[1]<<" "<<a[i][p[1]]<<endl;
p[2]=p[1]; bq[2]=a[i][p[1]];
}
else if(now[i]==3){
cout<<"1 "<<a[i][1]<<endl;
p[2]=1; bq[2]=a[i][1];
}
else if(now[i]==4){
cout<<p[1]<<" "<<a[i][p[1]]<<endl;
p[2]=p[1]; bq[2]=a[i][p[1]];
}
}
else if(i==3){
if(now[i]==1){
for(int j=1;j<=4;j++){
if(a[i][j]==bq[2]){
cout<<j<<" "<<a[i][j]<<endl;
p[3]=j;bq[3]=bq[2];
}
}
}
else if(now[i]==2){
for(int j=1;j<=4;j++){
if(a[i][j]==bq[1]){
cout<<j<<" "<<a[i][j]<<endl;
p[3]=j;bq[3]=a[i][j];
}
}
}
else if(now[i]==3){
cout<<"3 "<<a[i][3]<<endl;
p[3]=3; bq[3]=a[i][3];
}
else if(now[i]==4){
cout<<bj4[i]<<" 4"<<endl;
p[3]=bj4[i]; bq[3]=4;
}
}
else if(i==4){
if(now[i]==1){
cout<<p[1]<<" "<<a[i][p[1]]<<endl;
p[4]=p[1]; bq[4]=a[i][p[1]];
}
else if(now[i]==2){
cout<<"1 "<<a[i][1]<<endl;
p[4]=1; bq[4]=1;
}
else if(now[i]==3){
cout<<p[2]<<" "<<a[i][p[2]]<<endl;
p[4]=p[2]; bq[4]=a[i][p[2]];
}
else if(now[i]==4){
cout<<p[2]<<" "<<a[i][p[2]]<<endl;
p[4]=p[2]; bq[4]=a[i][p[2]];
}
}
else if(i==5){
if(now[i]==1){
for(int j=1;j<=4;j++){
if(a[i][j]==bq[1]){
cout<<j<<" "<<a[i][j]<<endl;
p[5]=j;bq[5]=a[i][j];
}
}
}
else if(now[i]==2){
for(int j=1;j<=4;j++){
if(a[i][j]==bq[2]){
cout<<j<<" "<<a[i][j]<<endl;
p[5]=j;bq[5]=a[i][j];
}
}
}
else if(now[i]==3){
for(int j=1;j<=4;j++){
if(a[i][j]==bq[4]){
cout<<j<<" "<<a[i][j]<<endl;
p[5]=j;bq[5]=a[i][j];
}
}
}
else if(now[i]==4){
for(int j=1;j<=4;j++){
if(a[i][j]==bq[3]){
cout<<j<<" "<<a[i][j]<<endl;
p[5]=j;bq[5]=a[i][j];
}
}
}
}
}
}
return 0;
}
D.The Lucky Week
Edward, the headmaster of the Marjar University, is very busy every day and always forgets the date.
There was one day Edward suddenly found that if Monday was the 1st, 11th or 21st day of that month, he could remember the date clearly in that week. Therefore, he called such week "The Lucky Week".
But now Edward only remembers the date of his first Lucky Week because of the age-related memory loss, and he wants to know the date of the N-th Lucky Week. Can you help him?
Input
There are multiple test cases. The first line of input is an integer T indicating the number of test cases. For each test case:
The only line contains four integers Y, M, D and N (1 ≤ N ≤ 109) indicating the date (Y: year, M: month, D: day) of the Monday of the first Lucky Week and the Edward's query N.
The Monday of the first Lucky Week is between 1st Jan, 1753 and 31st Dec, 9999 (inclusive).
Output
For each case, print the date of the Monday of the N-th Lucky Week.
Sample Input
2
2016 4 11 2
2016 1 11 10
Sample Output
2016 7 11
2017 9 11
思路
显然暴力会超时，所以就想是不是找规律，因为有闰年什么的一个一个判断也很麻烦。
发现400年是一个循环节，每400年内幸运周规律是一样的。
所以先暴力找1~400年的，然后把给的年份带进来除去循环节就好了。
代码
#include<cstdio>
#include<iostream>
using namespace std;
int a[3000][5];
int r;
void init(){
int yy,mm,dd;
r=0;
for(int i=0;i<400;i++){
for(int j=1;j<=12;j++){
for(int k=1;k<=30;k+=10){
yy=i;mm=j;dd=k;
if(mm==1||mm==2)
mm+=12,yy--;
int w=(dd+1+2*mm+3*(mm+1)/5+yy+yy/4-yy/100+yy/400)%7; //算星期
if(w==1){
a[r][1]=i;a[r][2]=j;a[r][3]=k;
r++;
}
}
}
}
}
int main(){
init();
int T;cin>>T;
while(T--){
int y,m,d,n;
cin>>y>>m>>d>>n;
n--;
int res=y/400;y%=400;
int flag;
for(int i=0;i<r;i++){
if(a[i][1]==y&&a[i][2]==m&&a[i][3]==d){
flag=i;
}
}
res+=(flag+n)/2058;
flag=(flag+n)%2058;
res=res*400+a[flag][1];
printf("%d %d %d\n",res,a[flag][2],a[flag][3]);
}
return 0;
}
I.People Counting
In a BG (dinner gathering) for ZJU ICPC team, the coaches wanted to count the number of people present at the BG. They did that by having the waitress take a photo for them. Everyone was in the photo and no one was completely blocked. Each person in the photo has the same posture. After some preprocessing, the photo was converted into a H×W character matrix, with the background represented by ".". Thus a person in this photo is represented by the diagram in the following three lines:
.O.
/|
(.)
Given the character matrix, the coaches want you to count the number of people in the photo. Note that if someone is partly blocked in the photo, only part of the above diagram will be presented in the character matrix.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first contains two integers H, W (1 ≤ H, W ≤ 100) - as described above, followed by H lines, showing the matrix representation of the photo.
Output
For each test case, there should be a single line, containing an integer indicating the number of people from the photo.
Sample Input
2
3 3
.O.
/|
(.)
3 4
OOO(
/|\
()))
Sample Output
1
4
思路
暴力,对于图上每个部件都一定有一个对应的人，所以我们就把所有的部件对应整个人的各个部位判断是不是匹配的，如果匹配就扣掉，直到整张图都被扣光。
代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000+10;
int n,m,ans;
char a[maxn][maxn];
void koutu(int x,int y){ // sxbk！
if(a[x][y]=='O'){
if(a[x+1][y]=='|')
a[x+1][y]='.';
if(a[x+1][y-1]=='/')
a[x+1][y-1]='.';
if(a[x+1][y+1]=='\\')
a[x+1][y+1]='.';
if(a[x+2][y-1]=='(')
a[x+2][y-1]='.';
if(a[x+2][y+1]==')')
a[x+2][y+1]='.';
}
else if(a[x][y]=='|'){
if(a[x-1][y]=='O')
a[x-1][y]='.';
if(a[x][y-1]=='/')
a[x][y-1]='.';
if(a[x][y+1]=='\\')
a[x][y+1]='.';
if(a[x+1][y-1]=='(')
a[x+1][y-1]='.';
if(a[x+1][y+1]==')')
a[x+1][y+1]='.';
}
else if(a[x][y]=='/'){
if(a[x-1][y+1]=='O')
a[x-1][y+1]='.';
if(a[x][y+1]=='|')
a[x][y+1]='.';
if(a[x][y+2]=='\\')
a[x][y+2]='.';
if(a[x+1][y]=='(')
a[x+1][y]='.';
if(a[x+1][y+2]==')')
a[x+1][y+2]='.';
}
else if(a[x][y]=='\\'){
if(a[x-1][y-1]=='O')
a[x-1][y-1]='.';
if(a[x][y-1]=='|')
a[x][y-1]='.';
if(a[x][y-2]=='/')
a[x][y-2]='.';
if(a[x+1][y-2]=='(')
a[x+1][y-2]='.';
if(a[x+1][y]==')')
a[x+1][y]='.';
}
else if(a[x][y]=='('){
if(a[x-2][y+1]=='O')
a[x-2][y+1]='.';
if(a[x-1][y]=='/')
a[x-1][y]='.';
if(a[x-1][y+1]=='|')
a[x-1][y+1]='.';
if(a[x-1][y+2]=='\\')
a[x-1][y+2]='.';
if(a[x][y+2]==')')
a[x][y+2]='.';
}
else if(a[x][y]==')'){
if(a[x-2][y-1]=='O')
a[x-2][y-1]='.';
if(a[x-1][y-2]=='/')
a[x-1][y-2]='.';
if(a[x-1][y-1]=='|')
a[x-1][y-1]='.';
if(a[x-1][y]=='\\')
a[x-1][y]='.';
if(a[x][y-2]==')')
a[x][y-2]='.';
}
a[x][y]='.';
return ;
}
void keller(){
int flag=1;
while(flag){
flag=0;
for(int i=4;i<=n+3;i++){
for(int j=4;j<=m+3;j++){
if(a[i][j]!='.'){
flag=1;
koutu(i,j);
ans++;
}
}
}
}
return ;
}
int main(){
int T;
cin>>T;
while(T--){
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
a[i][j]='.';
}
}
cin>>n>>m;
for(int i=4;i<=n+3;i++){
for(int j=4;j<=m+3;j++){
cin>>a[i][j];
}
}
ans=0;
keller();
cout<<ans<<endl;
}
return 0;
}
K.Highway Project
Edward, the emperor of the Marjar Empire, wants to build some bidirectional highways so that he can reach other cities from the capital as fast as possible. Thus, he proposed the highway project.
The Marjar Empire has N cities (including the capital), indexed from 0 to N - 1 (the capital is 0) and there are M highways can be built. Building the i-th highway costs Ci dollars. It takes Di minutes to travel between city Xi and Yi on the i-th highway.
Edward wants to find a construction plan with minimal total time needed to reach other cities from the capital, i.e. the sum of minimal time needed to travel from the capital to city i (1 ≤ i ≤ N). Among all feasible plans, Edward wants to select the plan with minimal cost. Please help him to finish this task.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first contains two integers N, M (1 ≤ N, M ≤ 105).
Then followed by M lines, each line contains four integers Xi, Yi, Di, Ci (0 ≤ Xi, Yi < N, 0 < Di, Ci < 105).
Output
For each test case, output two integers indicating the minimal total time and the minimal cost for the highway project when the total time is minimized.
Sample Input
2
4 5
0 3 1 1
0 1 1 1
0 2 10 10
2 1 1 1
2 3 1 2
4 5
0 3 1 1
0 1 1 1
0 2 10 10
2 1 2 1
2 3 1 2
Sample Output
4 3
4 4
思路
最短路+贪心
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=200000+10;
long long dis[maxn],cost[maxn],x,y;
int vis[maxn],nxt[maxn],cnt;
struct node{
int u,v,w,c,next;
}edge[maxn];
queue<int>q;
void add_edge(int u, int v, int w, int c){
edge[cnt] = {u, v,w,c,nxt[u]};;
nxt[u] = cnt++;
edge[cnt] = {v, u,w,c,nxt[v]};
nxt[v] = cnt++;
}
void init(){
memset(nxt,-1,sizeof(nxt));
memset(dis,0x7f,sizeof(dis));
memset(cost,0x7f,sizeof(cost));
memset(vis,0,sizeof(vis));
while(!q.empty()){
q.pop();
}
}
void spfa(){
q.push(1);
dis[1]=0;cost[1]=0;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=nxt[u];~i;i=edge[i].next){
int v=edge[i].v,w=edge[i].w,c=edge[i].c;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
cost[v]=c;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
else if(dis[v]==dis[u]+w){
if(cost[v]>c){
cost[v]=c;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
}
int main(){
int T,n,m,u,v,w,c;
cin>>T;
while(T--){
x=0;y=0;cnt=0;
init();
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v>>w>>c;
add_edge(u+1,v+1,w,c);
}
spfa();
for(int i=2;i<=n;i++){
x+=dis[i];
y+=cost[i];
}
cout<<x<<" "<<y<<endl;
}
return 0;
}
L.Very Happy Great BG
The summer training of ZJU ICPC in July is about to end. To celebrate this great and happy day, the coach of ZJU ICPC Team decided to BG everyone!
After a brief discussion, they decided to go to Lou Wai Lou to have a great dinner. Each team member can bring some friends with him/her. Of course, they need to tell the coach the number of friends they will bring.
Now the coach wants to know the total number of participants (excluding the coach himself). Please tell him.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains an integer N (1 <= N <= 40) - the number of ZJU ICPC members.
The second line contains N non-negative integers, the i-th integer indicates the number of friends (< 1000) that the i-th team member will bring.
Output
For each test case, output the total number of participants.
Sample Input
4
5
0 0 1 2 3
1
0
10
1 2 3 4 5 6 7 8 9 10
2
5 3
Sample Output
11
1
65
10
思路
水题，求个和就好了
代码
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=40+10;
int main(){
int T;
cin>>T;
while(T--){
int n;cin>>n;
int sum=n;
for(int i=1;i<=n;i++){
int x;cin>>x;
sum+=x;
}
cout<<sum<<endl;
}
return 0;
}