Entry date: August 17, 2021
Competition time: 8:00 ~ 11:00
Achievement: 100 + 40 + 100 + 10 = 250 (expected 300 +)
T1 garlic King eat cake
Problem description
Mr. garlic now has an n*m rectangular cake, If a{i,j} = * (asterisk), it means that the cake at this point is not clean and there is sand in it. If a{i,j} = (point), it means that the cake at this point is clean. Garlic gentleman can choose to eat one row or a column of cakes without sand at a time. He can eat unlimited times. Please ask him how many units of cake he can eat at the end.
Input format
The two integers in the first line represent n and m respectively.
Next n lines, each with a string of length m.
Output format
How many units of cake can you eat at last.
Data range
For 30% data, 1 ≤ n,m ≤ 10;
For the other 20%, the cake is guaranteed to contain no sand;
For 100% data, 1 ≤ n,m ≤ 1000.
Input and output requirements
It is required to use the method of "file input and output" to solve the problem. The input file is cake In, the output file is cake out
Overall thinking
The final answer = horizontal can eat - several columns can eat + vertical columns can eat
#include<bits/stdc++.h>
using namespace std;
bool t[1005][1005];
int n,m,ans=0,shu=0;
char a[1005][1005];
int main(){
freopen("cake.in","r",stdin);
freopen("cake.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
int flag=0;
for(int j=1;j<=m;j++){
if(a[i][j]=='*')
flag=1;
}
if(flag==0){
ans+=m;
shu++;
}
}
for(int j=1;j<=m;j++){
int flag=0;
for(int i=1;i<=n;i++){
if(a[i][j]=='*')
flag=1;
}
if(flag==0){
ans+=n-shu;
}
}
cout<<ans<<endl;
return 0;
}
Recurrence of T2 garlic gentleman
Problem description
Garlic Jun has learned about recursion. A very classic question is: give an n * n grid chessboard, and each move can only be right or down. How many schemes are there from (1,1) to (n,n)?
You have figured out the right way to solve this problem. But now the flower coconut girl ran out to make trouble when the garlic gentleman was doing calculations and hollowed out the m points on the grid, that is to say, she is not allowed to go to these hollowed out grids now, which can embarrass the garlic gentleman. Can you help him?
Input format
The first line of input contains two non negative integers n and m, which respectively represent the size of the grid and the number of hollowed out grids.
In the next m lines, two positive integers x and y not greater than N in each line indicate that the lattice of coordinates (x,y) is hollowed out. The title is guaranteed not to appear (1,1) and (n,n), but the same lattice may be hollowed out many times.
Output format
The output contains only one non negative integer, which is the result after the number of schemes% 100003.
Data range
For 20% data, n ≤ 3;
For 40% data, n ≤ 100;
For 100% data, n ≤ 1000,m ≤ 100000.
Input and output requirements
The method of "file input and output" is required to solve the problem. The input file is path In, the output file is path out
Overall thinking (dp)
If the current position is not hollowed out, dp[x][y]=dp[x-1][y]+dp[x][y-1], otherwise dp[x][y]=0
My cerebral palsy is not% 100003... 310 becomes 260 (I could have got 100 results 40)
#include<bits/stdc++.h>
using namespace std;
bool a[1005][1005];
int n,m;
int dp[1005][1005];
int main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
a[x][y]=true;
}
int flag=0;
for(int i=1;i<=n;i++){
if(a[1][i]==false && flag==0){
dp[1][i]=1;
}
else{
dp[1][i]=0;
flag=1;
}
}
flag=0;
for(int i=1;i<=n;i++){
if(a[i][1]==false && flag==0)
dp[i][1]=1;
else{
dp[i][1]=0;
flag=1;
}
}
for(int i=2;i<=n;i++){
for(int j=2;j<=n;j++){
if(a[i][j]==true)
dp[i][j]=0;
else
dp[i][j]=(dp[i-1][j]+dp[i][j-1])%100003;
}
}
cout<<dp[n][n];
return 0;
}
T3 garlic King introduction
Problem description
Garlic king recently fell in love with a clearance game, one of which is like this: players need to break through the city wall guarded by a fort. The game will take nn rounds in total. Players can't directly cross the city wall. The fort will accumulate a{i} points of energy at the beginning of each round, and each point of energy will cause a little damage to players.
The battery has m attack opportunities in total. The damage value of each attack is determined by the energy value of the battery at this time. Each attack will empty the energy value of the battery.
In this level of the game, players can choose the time to be attacked by the fort, that is, players can choose whether to be attacked by the fort in each round (the fort can only attack once in a round).
To get through this level, players must bear full m attacks, and in order to prevent speculation, players must bear attacks in the last round.
After each attack, as long as there is no death, the player will recover full health.
At the beginning, the player's maximum HP is 1. When the HP is less than or equal to 0, he dies. Now the garlic king wants to know how much equipment he must prepare to increase the maximum HP to pass this level?
Input format
The first line of input has two integers n and m, indicating that the game has n rounds and the number of attacks that the player needs to bear. A positive integer a{i} in each of the next N lines represents the energy points that the battery will accumulate at the beginning of each round of the game
Output format
Output garlic king at least need to prepare equipment that can increase HP to pass the game.
Data range
For 60% of the data, 1 ≤ n ≤ 1000, 1 ≤ m ≤ n,a{i} ≤ 1000;
For 100% of the data, 1 ≤ n ≤ 100000, 1 ≤ m ≤ n,a{i}
≤10000.
Input and output requirements
It is required to use the method of "file input and output" to solve the problem. The input file is game In, the output file is game out
Overall thinking
Two point answer
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005];
bool check(int x){
int sum=0,num=0;
for(int i=1;i<=n;i++){
if(a[i]>=x)
return false;
if(sum+a[i]<x){
sum+=a[i];
}
else{
sum=a[i];
num++;
}
}
if(sum>0)
num++;
if(num>m)
return false;
else
return true;
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int l=0,r=2e9;
int ans=r;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
r=mid-1;
ans=mid-1;
}
else
l=mid+1;
}
cout<<ans<<endl;
return 0;
}
T4 special connecting block of garlic King
Problem Description:
Garlic Jun recently learned the lesson "finding connected blocks by DFS". For a matrix of n * n containing only 01, the 1 adjacent to the top, bottom, left and right is the same connected block, for example:
1000 0101 0111 1000
This matrix contains three connected blocks of 1.
Now Mr. garlic wants to make himself more difficult. He changes the rules of connected blocks - no longer the same number belongs to the same connected block, but 0 and up, down, left and right 1 belong to the same connected block, and 1 and up, down, left and right 0 belong to the same connected block.
For example, the following is a connected block of size 4:
01 10
Now give a 01 matrix of n * n. every time you want to know how big the connected block of a lattice (x,y) is.
Input format
The first line of input contains two positive integers n,m.
The next N lines contain n characters, only 0 or 1, and there is no space between the characters.
Next, in row m, two positive integers x and Y separated by spaces in each row correspond to the lattice in row X and column y of the matrix, and ask how large the connected block of this lattice is.
Output format
The output has m lines, representing the result of each query.
Data range
For 20% of data, 1 ≤ n ≤ 10;
For 40% data, 1 ≤ n ≤ 50;
For 50% data, 1 ≤ m ≤ 5;
For 60% data, 1 ≤ n,m ≤ 100;
For 100% data, 1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000000.
Input and output requirements
It is required to use the method of "file input and output" to solve the problem. The input file is maze In, the output file is maze out
Overall thinking
Memory search
During the exam, I was out of my mind and wrote a program to search from the beginning every time. Sure enough, 10 points
#include<bits/stdc++.h>
using namespace std;
int n,m,now=0,cnt[1000005],vis[1005][1005];
char a[1005][1005];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool pd(int x){
return x>=0 && x<n;
}
void dfs(int x,int y){
cnt[now]++;
vis[x][y]=now;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(!vis[nx][ny] && pd(nx) && pd(ny) && a[x][y]!=a[nx][ny]){
dfs(nx,ny);
}
}
}
int main(){
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(vis[i][j]==0){
now++;
dfs(i,j);
}
}
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
cout<<cnt[vis[x-1][y-1]]<<endl;
}
return 0;
}