Pretty Matrix
Time Limit: 1 Second Memory Limit: 65536 KB
DreamGrid's birthday is coming. As his best friend, BaoBao is going to prepare a gift for him.
As we all know, BaoBao has a lot of matrices. This time he picks an integer matrix with rows and columns from his collection, but he thinks it's not pretty enough. On the one hand, he doesn't want to be stingy, but some integers in the matrix seem to be too small. On the other hand, he knows that DreamGrid is not good at algebra and hates large numbers, but some integers in the matrix seem to be too large and are not suitable for a gift to DreamGrid.
Based on the above consideration, BaoBao declares that a matrix is pretty, if the following conditions are satisfied:
- For every integer in the matrix, .
- For every integer in the matrix, .
where is the integer located at the -th row and the -th column in the matrix, and and are two integers chosen by BaoBao.
Given the matrix BaoBao picks, along with the two integers and , please help BaoBao change some integers in the matrix (BaoBao can change an integer in the matrix to any integer) so that the matrix becomes a pretty matrix. As changing integers in the matrix is tiring, please tell BaoBao the minimum number of integers in the matrix he has to change to make the matrix pretty.
Input
There are multiple test cases. The first line of input is an integer (about 100), indicating the number of test cases. For each test case:
The first line contains four integers , , and . (). Their meanings are described above.
For the next lines, the -th line contains integers (), representing the original matrix.
Output
For each test case output one line indicating the answer. If it's impossible to make the matrix pretty, print "No Solution" (without quotes) instead.
Sample Input
2
3 4 2 3
3 2 2 2
2 1 2 3
2 3 100 3
2 1 2 1
1
2
Sample Output
2
No Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false),cin.tie(),cout.tie();
int T;
cin>>T;
while(T--)
{
int n,m,a,b,ans=;
cin>>n>>m>>a>>b;
for(int i=; i<n; i++)
for(int j=,x; j<m; j++)
{
cin>>x;
if(x<a||x>b)ans++;
}
if(a>b)cout<<"No Solution\n";
else cout<<ans<<"\n";
}
return ;
}
PPAP
Time Limit: 1 Second Memory Limit: 65536 KB
"I have a pen. I have an apple. Uh! Applepen."
"I have a pen. I have pineapple. Uh! Pineapplepen."
The above lyrics are taken from PPAP, a single by Pikotaro. It was released as a music video on YouTube on 25 August 2016, and has since become a viral video. As of October 2017, the official video has been viewed over 126 million times.
Let's view this song from a mathematical perspective. In the lyrics there actually hides a function , which takes two lowercased string and as the input and works as follows:
- First, calculate ( here means string concatenation).
- Then, capitalize the first character of to get .
- Make as its output, and the function is done.
For example, we have PPAP("pen", "apple") = "Applepen", and PPAP("pen", "pineapple") = "Pineapplepen".
Given two lowercased strings and , your task is to calculate .
Input
The first line of the input contains an integer (about 100), indicating the number of test cases. For each test case:
The first and only line contains two strings and () separated by one space. It's guaranteed that both and consist of only lowercase English letters.
Output
For each test case output one line containing one string, indicating .
Sample Input
3
pen apple
pen pineapple
abc def
Sample Output
Applepen
Pineapplepen
Defabc
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false),cin.tie(),cout.tie();
int T;
cin>>T;
while(T--)
{
string s,c;
cin>>s>>c;
c[]-=;
cout<<c<<s<<"\n";
}
return ;
}
Mergeable Stack
Time Limit: 2 Seconds Memory Limit: 65536 KB
Given initially empty stacks, there are three types of operations:
1 s v: Push the value onto the top of the -th stack.
2 s: Pop the topmost value out of the -th stack, and print that value. If the -th stack is empty, pop nothing and print "EMPTY" (without quotes) instead.
-
3 s t: Move every element in the -th stack onto the top of the -th stack in order.
Precisely speaking, denote the original size of the -th stack by , and the original size of the -th stack by . Denote the original elements in the -th stack from bottom to top by , and the original elements in the -th stack from bottom to top by .
After this operation, the -th stack is emptied, and the elements in the -th stack from bottom to top becomes . Of course, if , this operation actually does nothing.
There are operations in total. Please finish these operations in the input order and print the answer for every operation of the second type.
Input
There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:
The first line contains two integers and (), indicating the number of stacks and the number of operations.
The first integer of the following lines will be (), indicating the type of operation.
- If , two integers and (, ) follow, indicating an operation of the first type.
- If , one integer () follows, indicating an operation of the second type.
- If , two integers and (, ) follow, indicating an operation of the third type.
It's guaranteed that neither the sum of nor the sum of over all test cases will exceed .
Output
For each operation of the second type output one line, indicating the answer.
Sample Input
2
2 15
1 1 10
1 1 11
1 2 12
1 2 13
3 1 2
1 2 14
2 1
2 1
2 1
2 1
2 1
3 2 1
2 2
2 2
2 2
3 7
3 1 2
3 1 3
3 2 1
2 1
2 2
2 3
2 3
Sample Output
13
12
11
10
EMPTY
14
EMPTY
EMPTY
EMPTY
EMPTY
EMPTY
EMPTY
卡函数，要用list的splice
就是这个合并很耗时间，用链表去模拟也是可以的
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+;
list<int>L[N];
int main()
{
ios::sync_with_stdio(false),cin.tie(),cout.tie();
int T;
cin>>T;
while(T--)
{
for(int i=; i<N; i++)L[i].clear();
int n,q;
cin>>n>>q;
while(q--)
{
int op;
cin>>op;
if(op==)
{
int a,b;
cin>>a>>b;
L[a].push_back(b);
}
else if(op==)
{
int a;
cin>>a;
if(L[a].size())
{
cout<<L[a].back()<<"\n";
L[a].pop_back();
}
else cout<<"EMPTY\n";
}
else
{
int a,b;
cin>>a>>b;
L[a].splice(L[a].end(),L[b]);
}
}
}
return ;
}
Traffic Light
Time Limit: 1 Second Memory Limit: 131072 KB
DreamGrid City is a city with intersections arranged into a grid of rows and columns. The intersection on the -th row and the -th column can be described as , and two intersections and are connected by a road if .
At each intersection stands a traffic light. A traffic light can only be in one of the two states: 0 and 1. If the traffic light at the intersection is in state 0, one can only move from to or ; If the traffic light is in state 1, one can only move from to or (of course, the destination must be another intersection in the city).
BaoBao lives at the intersection , and he wants to visit his best friend DreamGrid living at the intersection . After his departure, in each minute the following things will happen in order:
- BaoBao moves from his current intersection to another neighboring intersection along a road. As a law-abiding citizen, BaoBao has to obey the traffic light rules when moving.
- Every traffic light changes its state. If a traffic light is in state 0, it will switch to state 1; If a traffic light is in state 1, it will switch to state 0.
As an energetic young man, BaoBao doesn't want to wait for the traffic lights, and he must move in each minute until he arrives at DreamGrid's house. Please tell BaoBao the shortest possible time he can move from to to meet his friend, or tell him that this is impossible.
Input
There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:
The first line contains two integers and (), indicating the size of the city.
For the following lines, the -th line contains integers (), where indicates the initial state of the traffic light at intersection .
The next line contains four integers , , and (, ), indicating the starting intersection and the destination intersection.
It's guaranteed that the sum of over all test cases will not exceed .
Output
For each test case output one line containing one integer, indicating the shortest possible time (in minute) BaoBao can move from to without stopping. If it is impossible for BaoBao to arrive at DreamGrid's house, print "-1" (without quotes) instead.
Sample Input
4
2 3
1 1 0
0 1 0
1 3 2 1
2 3
1 0 0
1 1 0
1 3 1 2
2 2
1 0
1 0
1 1 2 2
1 2
0 1
1 1 1 1
Sample Output
3
5
-1
0
Hint
For the first sample test case, BaoBao can follow this path: .
For the second sample test case, due to the traffic light rules, BaoBao can't go from to directly. Instead, he should follow this path: .
For the third sample test case, it's easy to discover that BaoBao can only go back and forth between and .
按照要求dfs吧
#include <bits/stdc++.h>
using namespace std;
struct T
{
int x,y,f;
} tt;
int dir[]= {-,};
int solve()
{
int n,m;
scanf("%d%d",&n,&m);
int a[n+][m+],vis[n+][m+];
for(int i=; i<=n; i++)
for(int j=; j<=m; j++)
scanf("%d",&a[i][j]),vis[i][j]=;
int x,y,s,t,f=;
scanf("%d%d%d%d",&x,&y,&s,&t);
queue<T> q;
vis[x][y]=1,q.push({x,y,f});
while(!q.empty())
{
tt=q.front();
q.pop();
if(tt.x==s&&tt.y==t) return tt.f;
int op=(a[tt.x][tt.y]+tt.f)%;
if(op==)
{
for(int i=; i<; i++)
{
x=tt.x,y=tt.y+dir[i],f=tt.f+;
if(vis[x][y]||y<||y>m) continue;
vis[x][y]=,q.push({x,y,f});
}
}
else
{
for(int i=; i<; i++)
{
x=tt.x+dir[i],y=tt.y,f=tt.f+;
if(vis[x][y]||x<||x>n) continue;
vis[x][y]=,q.push({x,y,f});
}
}
}
return -;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)printf("%d\n",solve());
return ;
}