#include<stdio.h>
#include<string.h>
#include<algorithm>
int e[110][110],culture[110][110],country[110],visit[110];//Adjacency matrix of countries and cultures
int N,K,M,S,T,learn[110],ans;
int judge(int x,int y)//Judge whether there is any conflict between the learned culture and x countries
{
if(culture[ country[y] ][ country[x] ])return 0;
if(culture[ country[T] ][ country[y] ])return 0;//If the destination country is excluded
for(int i=1;i<=learn[0];++i)
{
if(culture[learn[y]][country[i]])return 0;
}
return 1;
}
int dfs(int deep,int dis)
{
if(ans!=-1 && dis>=ans)return 0;//Pruning operation
if(deep==T)
{
ans=dis;//Because of the reason of the previous sentence, the one who can come in must be a relatively small distance
return 1;
}
for(int i=1;i<=N;++i)//Ergodic adjacent edge
{
if(deep==i)continue;
if(visit[i]==0 && judge(deep,i))//If the culture he learned doesn't conflict with him
{
visit[i]=1;
learn[0]++;
learn[learn[0]]=country[i];
dfs(i,dis+e[deep][i]);//recursion
learn[0]--;
visit[i]=0;
}
}
return 1;
}
int main()
{
scanf("%d %d %d %d %d",&N,&K,&M,&S,&T);
for(int i=1;i<=N;++i)
scanf("%d",&country[i]);
for(int i=1;i<=K;++i)
for(int j=1;j<=K;++j)
scanf("%d",&culture[i][j]);
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
e[i][j]=9999;//Enough for the topic
for(int i=1;i<=M;++i)
{
int u,v,d;
scanf("%d %d %d",&u,&v,&d);
if(!culture[country[v]][country[u]] && country[u]!=country[v])
e[u][v]=std::min(e[u][v],d);//Don't reverse this order. It should be that if your country doesn't exclude me, I can go there, even though I exclude you
if(!culture[country[u]][country[v]] && country[u]!=country[v])
e[v][u]=std::min(e[v][u],d);
}
learn[0]=1;//Store what you have learned
learn[1]=country[S];
ans=-1;
memset(visit,0,sizeof(visit));
visit[S]=1;
dfs(S,0);
printf("%d\n",ans);
return 0;
}
32 cyber police
Author: Turbo time limit: 1S chapter: basic exercises (string)
Problem Description:
As an Internet policeman, your task is to monitor email to see if there are some sensitive keywords. However, some cunning suspect will change the alphabet order of some words to avoid checking. Please write a program to find the keywords in this adjusted order.
Input Description:
There are two lines of input. The first line is the keyword list and the second line is the sentence to be checked.
All words are in lowercase, separated by a space, and the number of words in each line is unlimited
Output Description:
The output is the adjusted keywords found in the sentence
Output according to the order in the keyword list
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
return *(char *)a - *(char *)b;
}
int main()
{
char key[2020][20],str[2020],c;
int i=0,j=0,flag[2020];//Indicates whether the keyword has appeared
while((c=getchar()) && c!='\n')
{
if(c==' '){key[i][j]='\0';j=0;i++;}
else key[i][j++]=c;
}
key[i][j]='\0';//Keyword entry completed
memset(flag,0,sizeof(flag));
while(scanf("%s",str)!=EOF)
{//A flash of light came up with a good way to compare two words
int len1=strlen(str);
qsort(str,len1,sizeof(str[0]),cmp);
for(int k=0;k<=i;k++)
{
int len2=strlen(key[k]);
if(len1==len2)//Only the same length can be compared
{
char temp[2020];
strcpy(temp,key[k]);
qsort(temp,len2,sizeof(temp[0]),cmp);
if(strcmp(temp,str)==0)flag[k]=1;
}
}
}
for(int coun=0,j=0;j<=i;j++)
if(flag[j]==1)printf(coun++==0?"%s":" %s",key[j]);
printf("\n");
return 0;
}
33 line segments and points
Author: Turbo time limit: 1S chapter: others
Problem Description:
There are n points and m intervals. The endpoints of points and intervals are all integers. For point a and interval [b,c], if a > = B and a < = C, point a is said to satisfy interval [b,c].
All points of the interval are minimized.
Input Description:
Two integers n m in the first line
The following n lines, each with an integer, represent the coordinates of the point
The following m lines have two integers per line, representing the range of the interval
1<=n,m<=10000
0 < = coordinates of points and intervals < = 50000
Output Description:
Output a line with the least number of points satisfying all intervals. If there is no solution, output - 1.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct lineNode
{
int left,right;
}line;
int cmp(const void *a,const void *b)
{
line x=*(line *)a,y=*(line *)b;
if(x.left!=y.left)return x.left - y.left;
else return x.right - y.right;
}
int main()//Sort the sections, and then traverse each section, and traverse each coordinate of the current section,
//The principle of traversal is to include as many intervals as possible, and you can't run out of any previous interval. If you run out, stop traversal and record the position of the largest point
{
int m,n,ans=0,x,y,temp,dot[51001];//Record the point and record the maximum number of intervals it can contain
line L[100001];
memset(L,0,sizeof(L));
memset(dot,0,sizeof(dot));
scanf("%d %d",&n,&m);
for(int i=0;i<n;++i){
scanf("%d",&temp);
dot[temp]=1;
}
for(int i=0;i<m;++i){
scanf("%d %d",&x,&y);
L[i].left=x;L[i].right=y;
}
qsort(L,m,sizeof(L[0]),cmp);
for(int i=0;i<m;++i){//Traverse all segments
int maxnum=-1;
for(int j=L[i].left;j<=L[i].right;++j){//Traverse all points
if(dot[j]){//If this point exists
dot[j]=1;//Be sure to reset to 1 Because it is possible that he assigned a large value in the operation of the previous group
for(int k=i+1;k<m;k++){
if(j>= L[k].left && j<=L[k].right)dot[j]++;
else break;
}
if(maxnum<dot[j])maxnum=dot[j];
}
}
if(maxnum==-1){printf("-1\n");return 0;}
ans++;
i=i-1+maxnum;//If it exists, count and filter out the included interval
}
printf("%d\n",ans);
return 0;
}
Our journey is the sea of stars
Author: Turbo time limit: 1S chapter: simulation
Problem Description:
The latest Mars exploration robot curiosity is trapped in a two-dimensional maze composed of squares.
There are four kinds of squares:
‘.’ Represents the open space, and curiosity can pass through it
'#' stands for obstacles, which cannot be crossed or stayed
'S' represents the starting position of curiosity
'T 'represents the destination of curiosity
NASA will send a series of commands to curiosity in the following format: "LRUD" represents one step to the left, right, up and down respectively. Because there are 55 million km between earth and Mars recently! Therefore, we must judge in advance what kind of state this series of instructions will make the curiosity in. Please complete it by programming.
Input Description:
The first line is an integer T, representing several test samples
The first line of each test sample is an integer n (1 < = n < = 50)) representing the size of the maze (N*N). The next N lines, each composed of N strings, represent the maze. The next line is an integer Q, which represents the number of queries. Each line of the next q is a string composed of only four letters of "LRUD", and the character conversion length is less than 1000
Output Description:
Output a separate line for each query:
“I get there!”: After executing the given command, the curiosity finally reaches the end point.
“I have no idea!”: The curiosity failed to reach the destination after executing the given command.
“I am dizzy!”: curiosity hit an obstacle while executing the command.
“I am out!”: On behalf of curiosity, he walked out of the boundary of the maze in the process of executing the command.
#include<stdio.h>
#include<string. h> / / simply simulate and write directly. Just control xy
int T,N,Q;
char maze[100][100],quest[2020];
void operate(int x,int y)
{
int len=strlen(quest);
for(int i=0;i<len;++i)
{
if(quest[i]=='R')y++;
else if(quest[i]=='L')y--;
else if(quest[i]=='U')x--;
else if(quest[i]=='D')x++;
if(x>N || x<1 || y>N || y<1)
{
puts("I am out!");
return;
}
else if(maze[x][y]=='#')
{
puts("I am dizzy!");
return;
}
else if(maze[x][y]=='T')
{
puts("I get there!");
return;
}
}
puts("I have no idea!");
}
int main()
{
scanf("%d ",&T);
while(T--)
{
memset(maze,0,sizeof(maze));
int x=0,y=0;//Coordinates of the starting position
scanf("%d ",&N);
for(int i=1;i<=N;++i)
{
for(int j=1;j<=N;++j)
{
scanf("%c",&maze[i][j]);
if(maze[i][j]=='S'){x=i;y=j;}
}
getchar();
}
scanf("%d ",&Q);
for(int i=1;i<=Q;++i)
{
gets(quest);
operate(x,y);
}
}
return 0;
}
35 fast power
Author: Turbo time limit: 1S chapter: mathematics related
Problem Description:
Given A, B, P, find (A^B) mod P.
Input Description:
Enter a total of one line.
The first line has three numbers, A, B, P.
A. B is a non negative integer in the range of long and P is a non negative integer in int.
Output Description:
Output a total of one line, indicating the required.
#include<stdio.h>
int main()//Fast power is regular
{
long long a,b,ans;
int p;
scanf("%lld %lld %d",&a,&b,&p);
ans=1;
a%=p;
while(b>0)
{
if(b&1)ans=ans*a%p;//Multiply odd numbers one more time
a=a*a%p;
b>>=1;//b divided by 2
}
printf("%d\n",ans);
return 0;
}
36 calendar
Author: Turbo time limit: 1S chapter: basic exercises (cycle)
Problem Description:
It is known that January 1, 2007 is Monday. Design a function to print the calendar of a year and a month after (including) 2007 according to the following format, and those before 2007 refuse to print. In order to complete this function, it is also necessary to design necessary auxiliary functions.
Input Description:
Two integers representing year and month, separated by spaces
Output Description:
Output by example
Note the number of spaces in each position, especially whether there are spaces at the end of each line.
#include<stdio.h>
int RunNian(int year)
{
return (year%400==0 ||(year%4==0 && year%100!=0));
}
int main()
{
int yy,mm,x,y,week=1;//0 for Sunday
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
scanf("%d %d",&x,&y);
for(yy=2007;yy<x;++yy)
{
int days=365;
if(RunNian(yy))days++;
days=days%7;
week=(week+days)%7;
}//It has been counted as the day of the week at the beginning of x years
if(RunNian(x))month[2]=29;
for(mm=1;mm<y;++mm)
{
week=(week+month[mm])%7;
}//What day of the week is the beginning of the month
printf("Calendar %d - %02d\n",yy,mm);//Start printing
printf("---------------------\n");
printf("Su Mo Tu We Th Fr Sa\n");
printf("---------------------\n");
int count=1;
for(int i=0;i<7;++i)//Print first line
if(i<week)printf(" ");
else printf("%2d ",count++);
printf("\n");
week=0;
while(count<=month[mm])
{
printf("%2d ",count++);
if(++week%7==0)printf("\n");
}
if(week%7!=0)printf("\n");
printf("---------------------");
return 0;
}
37 degree of separation
Author: Turbo time limit: 1S chapter: Enumeration
Problem Description:
In our increasingly connected world, people speculate that everyone is no more than six degrees apart from others. In this problem, you need to write a program to find the greatest separation in people's relationship network.
For any two people, their degree of separation is the minimum number of relationships needed to connect two people. For a relational network, the maximum separation degree is the maximum of the separation degree of any two people in the network. If two people in a network are not connected through a relationship chain, the network is not connected.
As shown in the figure below, a network can be described by some symmetrical relationships connecting two people. A line segment indicates a connection between two people. Network a describes a network with a maximum separation of 2, and network B is not connected.
Input Description:
The input contains multiple groups of data describing the relationship network. For each group of data, the first row has two numbers P, indicating the number of people in the network and R, the logarithm of the relationship. The next line is r relationships. Each relationship is represented by two strings, representing the names of two people in the network. Each name is different and there is no space in the middle. Because one person may be associated with more than one person, a name may appear multiple times in a set of data.
End with a line of two zeros.
2<=P<=50，R>=1
Output Description:
For each network, the maximum degree of separation in the output network. If the network is DISCONNECTED, output DISCONNECTED. After each network output, another carriage return is output. Output in the format in the sample output.
#include<stdio.h>
#Include < iostream > / / go straight to Freud
#include<string.h>
#include<map>
using namespace std;
map<string,int>people;
int edge[100][100];
int main()
{
int t=1,x,y;
char name1[100],name2[100];
while(scanf("%d %d",&x,&y)!=EOF && x+y)
{
people.clear();
memset(edge,0x3f3f3f3f,sizeof(edge));
int pos=1;
for(int i=0;i<y;++i)
{
scanf(" %s %s",name1,name2);
if(people[name1]==0)//If you are a new member
people[name1]=pos++;
if(people[name2]==0)//If you are a new member
people[name2]=pos++;
edge[people[name1]][people[name2]]=1;
edge[people[name2]][people[name1]]=1;
}
if(pos!=x+1)//If there are not enough people, it must be disconnected
{
printf("Network %d: DISCONNECTED\n\n",t++);
continue;
}
for(int k=1;k<=x;k++)
for(int i=1;i<=x;++i)
for(int j=1;j<=x;++j)//Remove yourself from your situation
if(i!=j && k!=i && k!=j && edge[i][k]+edge[k][j]<edge[i][j])edge[j][i]=edge[i][j]=edge[i][k]+edge[k][j];
int flag=1,dis=-1;
for(int i=1;i<=x && flag;++i)
for(int j=i+1;j<=x && flag;++j)
{
if(edge[i][j]==0x3f3f3f3f)flag=0;
if(edge[i][j]>dis)dis=edge[i][j];
}
if(!flag)printf("Network %d: DISCONNECTED\n\n",t++);
else printf("Network %d: %d\n\n",t++,dis);
}
return 0;
}
38 matrix flip
Author: Turbo time limit: 1S chapter: Enumeration
Problem Description:
Ciel has an NN matrix with an integer in each lattice.
N is an odd number, let X = (N+1)/2. Ciel can do this every time: he selects a sub matrix of XX from the matrix and multiplies all integers in the sub matrix by - 1.
Now let me ask you what the maximum sum of all numbers in the matrix can be after some operations.
Input Description:
The first line is a positive integer N.
The next N rows have N integers per row, representing the numbers in the initial matrix. The absolute value of each number shall not exceed 1000.
1 < = n < = 33, and N is odd.
Output Description:
Output an integer representing the maximum value of the sum of all numbers in the matrix after operation.
#include<stdio.h>
#include<stdlib.h>
#define max(a,b) a>b?a:b
int n,a[40][40],x,ans=-999999999;
void computing()
{
int maxnum=0,ta,tb;
for(int i=0;i<n;++i)maxnum+=a[x-1][i];
for(int i=0;i<x-1;++i)
{
ta=-999999999;
tb=a[i][x-1]+a[i+x][x-1];
for(int j=0;j<x-1;++j)tb+=abs(a[i][j]+a[i][j+x]+a[i+x][j]+a[i+x][j+x]);
ta=max(ta,tb);
tb=-1*(a[i][x-1]+a[i+x][x-1]);
for(int j=0;j<x-1;++j)tb+=abs( -1*a[i][j]+a[i][j+x]-a[i+x][j]+a[x+i][j+x] );
ta=max(ta,tb);
maxnum+=ta;
}
ans=max(maxnum,ans);
}
void solve()
{
for(int k=0;k<(1<<x-1);++k)//It must be a bit operation, or WA
{
for(int j=0;j<x-1;++j)
if((k&(1<<j))!=0)//Bit operation
{
for(int i=0;i<x;++i)
{
a[i][j]*=-1;
a[i][j+x]*=-1;
}
}
computing();
for(int j=0;j<x-1;++j)
if((k&(1<<j))!=0)//Bit operation
{
for(int i=0;i<x;++i)
{
a[i][j]*=-1;
a[i][j+x]*=-1;
}
}
}
}
int main()
{
scanf("%d",&n);
x=(n+1)/2;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)scanf("%d",&a[i][j]);
solve();
printf("%d\n",ans);
return 0;
}
39 maximum product
Author: Turbo time limit: 1S chapter: depth first search
Problem Description:
For n numbers, take m numbers from them. How to maximize the product of m numbers?
Input Description:
A number in the first row represents the number of data groups
Each group of input data has 2 lines in total:
The first line gives the total number of numbers N and the number of numbers m to be taken, 1 < = n < = m < = 15,
The second line gives the n numbers in turn, and the range of each number satisfies that the absolute value of a[i] is less than or equal to 4.
Output Description:
Each group of data outputs 1 line, which is the maximum product.
#include<stdio.h>
int T,m,n,num[20],ans,flag[20];
void dfs(int sum,int deep)//Put the results in the parameters to save time
{
if(deep>m)return;//prune
if(deep==m)
{
ans=ans>sum?ans:sum;
return;
}
for(int i=0;i<n;++i)
{
if(flag[i]==0)
{
flag[i]=1;
dfs(sum*num[i],deep+1);
flag[i]=0;
}
}
}
int main()//The catch-up of arrangement and combination, ruthless TLE. Add a prune
{
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;++i)
{
scanf("%d",&num[i]);
flag[i]=0;
}
ans=-999999999;
dfs(1,0);//Count from 0
printf("%d\n",ans);
}
return 0;
}
40 arrangement number
Author: Turbo time limit: 1S chapter: depth first search
Problem Description:
There are six full permutations of 0, 1 and 2, which are arranged in alphabetical order as follows:
012,021,102,120,201,210
Enter a number n
Find the nth in the total arrangement of 0 ~ 9 ten numbers (the first is 0123456789).
Input Description:
A line containing an integer n
Output Description:
A row containing a full array of 10 numbers
#include<stdio.h>
int n,num[20],flag[20],pos,ans;
void dfs(int sum,int deep)
{
if(deep==10)
{
ans++;
if(ans==n)
{
for(int i=0;i<=pos;++i)printf("%d",num[i]);
printf("\n");
}
return;
}
for(int i=0;i<10;++i)
{
if(flag[i]==0)
{
flag[i]=1;
num[++pos]=i;
dfs(10*sum+i,deep+1);
--pos;
flag[i]=0;
}
}
}
int main()//Arrange and combine. Open whole
{
scanf("%d",&n);
pos=-1;
dfs(0,0);
return 0;
}