SDUT 2022 Summer Individual Contest - 12(for 21）
——————水赛总结
A - Window
Jerry Smith is Rick's Son-in-Law and Morty's father. He recently moved out to a different neighborhood. Unfortunately Jerry is not very Smart or Bright. The new neighborhood is full of annoying children, Jerry is not able to sleep, eat, relax or find a moment of peace! One day, some children were playing outside and they broke Jerry's rectangular window. Jerry was furious and he decided to ask the children's parents to replace the broken window. He gave them the length X and width Y of the broken window. Unfortunately, when the child's parents brought him the new one, he discovered that he told them the dimensions in the wrong order. He gave them the dimensions as Y, X instead of X,Y. Needless to say, Jerry tends to do stupid things somtimes! Now Jerry needs your help in figuring out the area of the new window with the reversed dimensions so he can put it to good use instead of wasting it. Can you help him with that? Note that you will be given the dimensions as X, Y, your task is figuring the area formed by the rectangular window with dimensions Y, X.
Input
Your input will start with (1 ≤ T ≤ 100), number of test cases. Then T test cases follow. Each test case consists of a single line that contains two space separated integers X and Y (1 ≤ X, Y ≤ 105).
Output
For each test case you will print a single integer, the area of the rectangle with the dimensions Y and X.
Sample 1
| Inputcopy | Outputcopy |
|---|---|
3 5 4 1 2 33 33 | 20 2 1089 |
水
但是交文件的操作给我整懵了hh
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 17*/
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=1005;
//
int t;
signed main(){
freopen("window.in","r",stdin);
IOS;
cin>>t;
ll x,y;
ll res;
while(t--){
cin>>x>>y;
res=x*y;
cout<<res<<endl;
}
}
//made by shun 20220720B - Paper Game
Hasan and Hussain are playing a game with W × H paper, the game consist of turns; Hasan starts first. On each turn, the player chooses one of the pieces of paper and cuts it into two papers such that the cut must be a straight line parallel to one of the paper sides and must cut the paper to two pieces of paper with integer dimensions.
The loser is the one who can't make a move (i.e when all pieces of paper become 1 × 1). Assuming that Hasan and Hussain are playing optimally, who will win the game?
Input
The first line of input is an integer T(1 ≤ T ≤ 101) which represents the number of test cases. Each of the next T lines consists of two space-separated integers W,H (1 ≤ W,H ≤ 100,000) the width and the height of the paper.
Output
For each test case, output a single line representing its answer; if Hasan is the winner output "Hasan" (without quotes) otherwise "Hussain" (without quotes).
Sample 1
| Inputcopy | Outputcopy |
|---|---|
3 1 1 2 1 2 2 | Hussain Hasan Hasan |
博弈，最多裁剪次数为长*宽-1，所以可以直接判断
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 17*/
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=1005;
//
ll x,y;
int t;
signed main(){
IOS;
cin>>t;
while(t--){
cin>>x>>y;
if(x*y%2) cout<<"Hussain"<<endl;
else cout<<"Hasan"<<endl;
}
}
//made by shun 20220720C - Rectangles
You have n rectangles, each of which is described by three integers i, j and k. This indicates that the lower-left corner of the rectangle will be located at the point (i, 0) and the upper-right corner of the rectangle will be located at the point (j, k). For example, if you have a description of four rectangles like this: 0 2 3 0 3 1 1 2 2 2 4 4 The area occupied by these rectangles will be as follows:
The total area in this case will be 14. You are given n and n triples (i, j, k), your task is to compute the total area occupied by the rectangles which are described by the n triples.
Input
The first line will contain a single integer T indicates the number of test cases. Each test case will consist of n + 1 lines, the first one will contain the number of rectangles n and the following n lines will be the description of the rectangles. Each description will be a triple (i, j, k) as mentioned above. The Constraints: 10 <= T <= 20 1 <= n <= 100 0 <= i < 100 1 <= j < 100 i != j 1 <= k <= 100
Output
For each test case, print a single integer in a separated line indicates the total area occupied by the rectangles.
Sample 1
| Inputcopy | Outputcopy |
|---|---|
1 4 0 2 3 0 3 1 1 2 2 2 4 4 | 14 |
水题，直接暴力，bool一个数组判是否访问过，然后++就完了
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 18*/
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=105;;
//
int t,n;
bool st[N][N];
signed main(){
IOS;
cin>>t;
int a,b,c;
while(t--){
mem(st,false);
cin>>n;
int res=0;
for(int i=0;i<n;i++){
cin>>a>>b>>c;
for(int i=a;i<b;i++){
for(int j=0;j<c;j++){
if(!st[i][j]){
res++;
}
st[i][j]=true;
}
}
}
cout<<res<<endl;
}
}
//made by shun 20220721D - Sequences
One of the most wonderful qualities of an ACMer is to be multi interests so he combines multiple qualifications and hobbies not just coding. Hussain is one of the most qualified ACMers to mention when talking about hobbies and other domains of personality training despite of his qualifications in ACM problem solving and math. It's very known about Hussain his obsession in hunting and shooting, he used to pass hours training on empty cans in his childhood. These days, Hussain became a professional and still challenge others in this game, but for his bad luck he accidentally challenged a professional ACMer, without mentioning the name, so this ACMer made a game for Hussain. He numbered N targets for Hussain with random numbers and challenged him to shoot the minimum number of targets so the remaining numbers will form a sequence of increasing (by one) numbers in their current order. Example: if there is 6 targets numbered as follow: 2 5 7 3 2 4 Hussain will shoot 5,7 and the second 2 remaining for 2 3 4. Now, Hussain will focus on shooting, we will help him and focus on the targets he must shoot. But No! Hussain is an very good ACMer, we will make it hard for him and just tell him the number of the remaining targets in the sequence.
Input
First line contain an integer T represents the number of test cases 0 < T < 100, each test case consists of two lines, the first one is an integer 0< N < 20000 represents the number of targets, then followed by the second line that contains N numbers each number 0 < Xi < 20000 represents the number written on the i'th target.
Output
For each test case print one number represents the remaining sequence’s length can be created by the input where it should be the maximum length and each number of it follow its previous by 1.
Sample 1
| Inputcopy | Outputcopy |
|---|---|
4 6 2 5 7 3 2 4 7 2 18 65 33 11 5 4 5 2 7 5 9 3 5 9 8 7 10 11 | 3 1 2 3 |
Note
Please consider a large input file.
水，递增序列
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 18*/
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=20005;
//
int t,n;
int a[N];
signed main(){
IOS;
cin>>t;
ll x,y;
while(t--){
cin>>n;
mem(a,0);
int x;
int num=0;
for(int i=0;i<n;i++){
cin>>x;
a[x]=a[x-1]+1;
if(a[x]>num){
num=a[x];
}
}
cout<<num<<endl;
}
}
//made by shun 20220721E - Napoléon
In the world of chess, there is a good plan to start your game with which is “Napoléon plan”. “Napoléon plan” is commonly based on two pieces, (the queen and a bishop), using these two pieces you can guarantee the win after some moves if you are facing a beginner opponent or any way you can start your game with it to explore your opponent qualifications. Further, this plan can be used and applied in proceeding states of your game so you can disperse your opponent before you surprise him/her with a successful apply of “Napoléon plan” and saying your mortal word “checkmate”.
The plan; substantially, says that you can checkmate your opponent king by constricting it with its allies, threatening it with your queen which is guarded; commonly, by your bishop.
The picture displays a successful apply of “Napoléon plan”.
Our problem goes in a further state of the game, when you need to get your bishop to the right state guarding your queen for a successful apply of the plan. Given the Current location of the bishop and its Target state in the form Xc, Yc, Xt, Yt starting the count from zero, tell the queen: the minimum number of squares that the bishop pass in the minimum moves assuming an empty chess board.
Input
The first line of input is the number of test cases 0<T<5000, the second line is an integer for the chessboard size 0<N<=20, then (2*T) lines follow. Each test case is two lines; the first line contains two integers 0<=Xc,Yc<N representing the current location of the bishop, the second line contains another two integers 0<=Xt,Yt<N representing the target location of the bishop.
Output
For each test case, print a line containing the minimum number of squares passed by the bishop on its way to the target location taking the minimal possible moves or print “can't reach!” in case of impossible to reach the target from the current location.
Sample 1
| Inputcopy | Outputcopy |
|---|---|
3 8 0 0 7 1 5 5 5 5 0 5 6 7 | 7 0 6 |
两种解法，常规bfs做，或者直接取abs的max，因为这玩意只能斜着走（百度了一下才知道），而因为这个性质也就导致了起点终点的奇偶性相同才能成功到达。
//bfs做法（made by whale）
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <bits/stdc++.h>//
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
using namespace std;
const int N = 1e5 + 10;
bool vis[30][30];
int d[30][30];
int sa, sb, ea, eb;
int n;
struct node
{
int x, y;
};
int bfs()
{
queue<node> q;
q.push({sa, sb});
vis[sa][sb] = 1;
d[sa][sb] = 0;
while (!q.empty())
{
node k = q.front();
q.pop();
if (k.x == ea && k.y == eb)
return d[k.x][k.y];
else
{
if (k.x + 1 <n&&k.y+1<n&&!vis[k.x + 1][k.y+1])
{
vis[k.x + 1][k.y+1] = 1;
d[k.x+1][k.y+1]=d[k.x][k.y]+1;
q.push({k.x + 1, k.y+1});
}
if (k.x - 1>=0&&k.y+1<n&&!vis[k.x - 1][k.y+1])
{
vis[k.x - 1][k.y+1] = 1;
d[k.x-1][k.y+1]=d[k.x][k.y]+1;
q.push({k.x - 1, k.y+1});
}
if(k.y-1>=0&&k.x+1<n&&!vis[k.x+1][k.y-1])
{
vis[k.x+1][k.y-1]=1;
d[k.x+1][k.y-1]=d[k.x][k.y]+1;
q.push({k.x+1,k.y-1});
}
if(k.y-1>=0&&k.x-1>=0&&!vis[k.x-1][k.y-1])
{
vis[k.x-1][k.y-1]=1;
d[k.x-1][k.y-1]=d[k.x][k.y]+1;
q.push({k.x-1,k.y-1});
}
}
}
return -1;
}
int main()
{
IOS;
int t;
cin >> t;
cin >> n;
for (int i = 1; i <= t; i++)
{
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
cin >> sa >> sb >> ea >> eb;
int f=bfs();
if(f==-1)
cout<<"can't reach!"<<endl;
else
cout<<f<<endl;
}
return 0;
}
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 18*/
//技巧做法
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=105;;
//
int t,n;
signed main(){
IOS;
cin>>t;
int n;
cin>>n;
int a,b,x,y;
while(t--){
cin>>a>>b;
cin>>x>>y;
if((a+b)%2!=(x+y)%2){
cout<<"can't reach!"<<endl;
continue;
}
int res=max(abs(x-a),abs(y-b));
cout<<res<<endl;
}
}
//made by shun 20220721
F - The Best Strategy
Carlo Ancelotti "Real Madrid's coach" is so Sad and disappointed, and Florentino Perez fired him after getting knocked out from the UEFA Champions League against Juventus. Carlo is so good in algorithms and strategies (he is an engineer), and he heard about the ACM competition and decided to train a team to qualify to ICPC. After 2 years of training Carlo became really experienced with his team, and now he knows how much time his team needs to solve a problem (read it and code it correctly). Given the required solving time for each problem, help Carlo to determine the highest number of problems his team can solve with the minimum possible penalty.
The total penalty is the sum of penalties for all solved problems. The penalty for a solved problem is equal to the number of minutes which have passed after the starting of the contest when this problem is submitted. And the period of the contest is 300 minutes.
Input
Your program will be tested on one or more test cases. The first line of the input contains a single integer T (1 ≤ T ≤ 100) the number of test cases. Followed by T test cases. Each test case consists of two lines. The first line contains a single integer N (8 ≤ N ≤ 15), the number of problems .The next line consists of N integers separated by a single space: pi (4 ≤ pi ≤ 300) which refers to the solving time for each problem.
Output
For each test case print the highest number of problems his team can solve and the minimum possible penalty.
Sample 1
| Inputcopy | Outputcopy |
|---|---|
2 8 252 244 6 109 294 31 67 270 8 218 48 273 69 281 224 250 193 | 4 360 2 165 |
大水题，不多解释
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 17*/
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=1005;
//
ll x,y;
int t;
int n;
int a[20];
signed main(){
IOS;
cin>>t;
while(t--){
cin>>n;
for(int i =0;i<n;i++) cin>>a[i];
sort(a,a+n);
int res=0,num=0,sum=0;
for(int i=0;i<n;i++){
num+=a[i];
res++;
sum+=num;
if(num+a[i+1]>300) break;
}
cout<<res<<' '<<sum<<endl;
}
}
//made by shun 20220720G - Cutie Pie
Consider a NxM small-letters grid. SVU asked you to check whether this grid is a Cutie Pie or not A grid is a cutie pie if you can find the word "pie" in any direction (vertical, horizontal, and radial). Your program should output "Cutie Pie!" if the grid contains the word "pie" or "Sorry Man" otherwise
Input
The first line contains T 1<=T<=10000 the number of test cases. The followed T lines represent the test cases, each one contains two integers 0 < N,M ≤ 20 then N lines each of them contains M English small-letter separated by space characters. There is a blank line between each two successive test cases.
Output
For each test case output "Cutie Pie!" if the grid in the test case contains the word "pie" or "Sorry Man" otherwise.
Sample 1
| Inputcopy | Outputcopy |
|---|---|
2 3 5 o p r d t i i i i e f f s e d 4 3 o p r o k r i i u f f s | Cutie Pie! Sorry Man |
第一个深绿的题！欧耶！！！
暴力判就ok，很水很水
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 17*/
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=1005;
//
int t;
char a[25][25];
int n,m;
signed main(){
IOS;
cin>>t;
while(t--){
mem(a,0);
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j =0;j<m;j++) cin>>a[i][j];
}
int flag=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]=='p'){
if((a[i][j+1]=='i'&&a[i][j+2]=='e')||(a[i][j-1]=='i'&&a[i][j-2]=='e')||(a[i-1][j]=='i'&&a[i-2][j]=='e')||(a[i+1][j]=='i'&&a[i+2][j]=='e')||(a[i-1][j-1]=='i'&&a[i-2][j-2]=='e')||(a[i-1][j+1]=='i'&&a[i-2][j+2]=='e')||(a[i+1][j-1]=='i'&&a[i+2][j-2]=='e')||(a[i+1][j+1]=='i'&&a[i+2][j+2]=='e')){
cout<<"Cutie Pie!"<<endl;
flag=1;
break;
}
}
}
if(flag==1) break;
}
if(flag==0) cout<<"Sorry Man"<<endl;
}
}
//made by shun 20220720
H - Weekend
You and your friends are going to camping next weekend , because you are the best driver and you are living in this town for ten years , you have to drive the car from your home and pick up each of your friends to take them with you ,then finally go to the camping site. You have the map of the town and the length of every street ,and homes of friends will be at some intersections. you want to start from your home then pick up all of your friends then go to the camping site as fast as you can so you have to find the shortest path to do that. you can pick up your friends in any order but you have to make sure you pick up all of them. NOTE: you can pass by any intersection more than once including home and camping site .
Input
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 50). Followed by the test cases, the first line of each test case contains three integers N,M,F (3 ≤ N ≤ 100 , 0<M ≤ (N*(N-1))/2 , 1 ≤ F ≤ 9 ) representing the number of intersections , the number of streets and number of friends respectively. Followed by M lines, each line contains 3 integers separated by a single space X Y Z (1 ≤ X, Y ≤ N), (1 ≤ Z ≤ 1000) which represent a street between intersection X and intersection Y with length Z in both direction (X and Y will be different). then follow F (1<fr<N) deferent integer representing friends home number(number of intersection where home is located). your home is at intersection number one and camping site is at intersection number N.
Output
For each test case print a single line containing "Case n:" (without quotes) where n is the test case number (starting from 1) followed by a space then the shortest path to go from your home to camping site after picking up all your friends .
Sample 1
| Inputcopy | Outputcopy |
|---|---|
2 4 4 2 1 4 3 1 2 2 2 3 2 3 4 2 2 3 6 8 2 1 2 1 2 3 2 3 6 3 1 4 11 4 5 2 5 6 20 5 3 5 4 3 10 4 5 | Case 1: 6 Case 2: 20 |
Note
in the second test case the shortest path is : 1 > 2 > 3 > 5 > 4 > 5 > 3 > 6
Sponsor
没做出来，当时太累了，趴着睡着了。。。
弗洛伊德➕dfs全排列，问了一下旁边的大神，太强了
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 18*/
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=1e5+5;
//
int t;
int tt;
int ans;
int n,m,f;
int g[105][105];
int q[10];
int path[10];
bool st[10];
//
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
//
void dfs(int u){
if(u>f){
int res=g[1][path[1]];
for(int i=2;i<=f;i++) res+=g[path[i-1]][path[i]];
res+=g[path[f]][n];
ans=min(ans,res);
return ;
}
for(int i=1;i<=f;i++){
if(!st[i]){
path[u]=q[i];
st[i]=true;
dfs(u+1);
path[u]=0;
st[i]=false;
}
}
}
//
signed main(){
//IOS;
cin>>t;
for(tt=1;tt<=t;tt++){
mem(g,0x3f);
for(int i=0;i<10;i++) path[i]=q[i]=st[i]=0;
for(int i=0;i<=n;i++) g[i][i]=0;
cin>>n>>m>>f;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
floyd();
for(int i=1;i<=f;i++) cin>>q[i];
ans=0x3f3f3f3f;
dfs(1);
printf("Case %d: %d\n",tt,ans);
}
}
//made by shun 20220721
I - Playing With Strings
Dani and Mike are two kids ,They are playing games all day and when they don't find a game to play they invent a game . There is about an hour to arrive to school, because they love playing with strings Dani invented a game , Given a string and the winner is the first who form a palindrome string using all letters of this string according to the following sample rules : 1- player can rearrange letters to form a string . 2- the formed string must be palindrome and use all letters of the given string. 3- if there is more than one string chose the lexicographically smallest string . EX: string is "abacb" player can form : "abcba" and "bacab" ,but "abcba" is the lexicographically smallest. Mike asked you to write a Program to compute the palindrome string so he can beat Dani.
Input
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 1000). Every test case on one line contain one string ,the length of the string will not exceed 1000 lower case English letter.
Output
For each test case print a single line containing the lexicographically smallest palindrome string according to the rules above. If there is no such string print "impossible"
Sample 1
| Inputcopy | Outputcopy |
|---|---|
4 abacb acmicpc aabaab bsbttxs | abcba impossible aabbaa bstxtsb |
Note
Palindrome string is a string which reads the same backward or forward.
暴力模拟 没啥好说的，借鉴了队友的码hhhh，感谢鑫神帮我稳榜
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 18*/
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=1005;
//
map<char,int> mp;
int t;
signed main(){
IOS;
cin>>t;
while(t--){
mp.clear();
string s;
cin>>s;
int len=s.size();
int sum=0;
for(int i=0;i<len;i++){
mp[s[i]]++;
}
char c;
for(char i='a';i<='z';i++){
if(mp[i]%2){
sum++;c=i;
}
}
if(sum>1) cout<<"impossible"<<endl;
else{
string ans="";
for(char i='a';i<='z';i++){
if(mp[i]){
for(int j=1;j<=mp[i]/2;j++) ans+=i;
}
}
if(sum!=0) ans+=c;
for(char i='z';i>='a';i--){
if(mp[i]){
for(int j=1;j<=mp[i]/2;j++) ans+=i;
}
}
cout<<ans<<endl;
}
}
}
//made by shun 20220721
J - Good Coins
It was a beautiful day, the sun was shining, the sky was clear and king Omar was listening to the birds peacefully under his favorite apple tree. Suddenly, an apple fell down and hit his head, and an idea came to him, he decided to reduce the types of coins in his kingdom to two types only. To take a wise choice, he had to choose good coins. We call a group of two coins good if we can exchange any integer amount of money by using them. For example, you can exchange any amount of money by using coins which have the values 3 and 4 so the group {3, 4} is good but you can’t exchange the amount 3 if the two coins have the values 2 and 6, so the group {2, 6} isn’t good. You are about to help king Omar to choose a good group of coins to be the national coins from a set of choices. You program have to test T group of two members where 0<T<5000, and print “GOOD” if the group is good, and “NOT GOOD” if it is not.
Input
The first line of the input contains T the number of test cases, followed by T lines, each line contains tow integers x,y separated by a space and 0 < x,y ≤ 10 ^{} 7
Output
For each line of the input print “GOOD” if {x,y} is good and “NOT GOOD” if it is not.
Sample 1
| Inputcopy | Outputcopy |
|---|---|
4 3 4 2 6 19739 6101 3636 351 | GOOD NOT GOOD GOOD NOT GOOD |
Note
If someone X wants to give another one Y the amount 4 and the available coins have the values 3 and 5, then X can give Y 8 coins of the value 5 and Y give X 12 coins of the value 3 . 8x5-12x3=4
水题，gcd为1就good，否则就not
/*Where there is light, in my heart.*/
/*SUMMER_TRAINING DAY 18*/
#include<bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
//#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map<a,b>
#define unset(a) unordered_set<a>
#define F first
#define S second·
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
typedef double db;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> vi;
const int N=1005;
//
int gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
int t;
signed main(){
IOS;
cin>>t;
ll x,y;
while(t--){
cin>>x>>y;
if(gcd(x,y)==1) cout<<"GOOD"<<endl;
else cout<<"NOT GOOD"<<endl;
}
}
//made by shun 20220721总结：这应该是补题 最多的一次了，这次的题目总体来说都不是很难，关键是思维想法，其次是读题要快速的get到点上，这次很侥幸霸榜了第一很长时间，很开心，也拿了两个深绿，很有成就感的一件事情，虽然最后因为H掉了下去，但是说实话第一 的位置本也不属于我，有幸趁着这次的难度登了一次榜首，在开心的同时也要明白自己不会的东西还是太多了，然后我认为几个点比上次有了进步，一个就是读题更加扎实了，基本能做到一发过（除了奇怪的a题），第二个就是思维仍旧保持着，虽然比不过很多思维活跃的大佬，但是感觉自己的智商不能说不够用hh，最后就是debug的能力逐步提升了，码的速度也快了点，可能还是题简单的原因 吧
不足的地方仍然有很多，包括对涉及到较难算法的时候经常卡壳，然后是一个题总是没有更加灵活多变的思路，我认为一定要面对一个题有很多不同的思路才对，总而言之，思路不足还是会的东西太少了，基础还需要加强。