@CQUPTacm
2018-04-20T22:00:03.000000Z
字数 16188
阅读 2169
题解
本题的关键之处在于“当前方向”。解释一下样例也许各位就明白了:
初始:位于(0,0),面向北方。
第一步:向后转,前进100。此时位于(0,-100),面向南方。
第二步:向右转。此时位于(0,-100),面向西方。
第三步:前进10。此时位于(-10,-100),面向西方。
第四步:找到宝藏。输出-10 -100。
另外有一个值得注意的地方,每次移动的距离最多是100000,最多行动的次数是100000,也就是说,如果一直向前移动100000,移动100000次,最后的位置是(0,100000*100000),而int的上限是2^31-1。你们可以按一下计算器,比较一下。所以本题的位置要用long long来储存。
ps:首页提示的第一条就提到了“爆int”的情况。
时间复杂度o(行动数),空间复杂度o(1)。
代码
//C++
#include<iostream>
#include<stdio.h>
using namespace std;
int dic[4][2]={0,1,1,0,0,-1,-1,0}; //四个方向的位移影响
char s[6];
int main()
{
long long nx=0,ny=0; //当前位置
int d=0,x; //d是当前方向的编号
while(scanf("%s",s))
{
if(s[0]=='F')
break;
if(s[0]=='W')
{
scanf("%d",&x);
nx+=dic[d][0]*x;
ny+=dic[d][1]*x;
}
if(s[0]=='S')
{
d=(d+2)%4;
scanf("%d",&x);
nx+=dic[d][0]*x;
ny+=dic[d][1]*x;
}
if(s[0]=='D')
d=(d+1)%4;
if(s[0]=='A')
d=(d-1+4)%4;
}
printf("%lld %lld\n",nx,ny);
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int[][] dic={{0,1},{1,0},{0,-1},{-1,0}}; //四个方向的位移影响
long nx=0,ny=0; //当前位置
int d=0,x; //d是当前方向的编号
String s;
while(true){
s=cin.next();
if(s.equals("Find!"))
break;
if(s.equals("W")){
x=cin.nextInt();
nx+=dic[d][0]*x;
ny+=dic[d][1]*x;
}
if(s.equals("S")){
d=(d+2)%4;
x=cin.nextInt();
nx+=dic[d][0]*x;
ny+=dic[d][1]*x;
}
if(s.equals("D"))
d=(d+1)%4;
if(s.equals("A"))
d=(d-1+4)%4;
}
System.out.println(nx+" "+ny);
}
}
很多同学对题目的理解有误,所以我们先来理一下题目。
首先我们输出数字的前提,是“能找到是哪一米的水管出问题了”。换句话说,只剩一米水管有嫌疑的情况下,我们才能确定,是这一米水管出问题了。
反过来,如果不止一米水管有嫌疑,那么我们就不能确定答案,应该输出“No response!”。
许多同学对“数据保证有且仅有一处水管断裂,并且断裂不出现在整数米处。”这句话产生了误解。这句话表达的含义其实是:至少剩一米水管有嫌疑,不可能出现所有水管都是完好的。
所以我们把水管分成L段1米长的。对于每次检查,把提到的那些段水管的嫌疑都去掉,最后计算还有几段水管有嫌疑,如果只有一段,就输出答案,否则输出“No response!”。
时间复杂度o(L*M),空间复杂度o(L)。
//C++
#include<iostream>
#include<stdio.h>
using namespace std;
bool life[1005]; //life为0代表有嫌疑
int main()
{
int l,m,x,y,ans,flag=0; //flag是有嫌疑的段数,ans是有嫌疑的段左边的位置
scanf("%d%d",&l,&m);
while(m--)
{
scanf("%d%d",&x,&y);
for(int i=x;i<y;i++)
life[i]=1;
}
for(int i=0;i<l;i++)
{
if(!life[i])
{
ans=i;
flag++;
}
}
if(flag>1)
printf("No response!\n");
else
printf("%d\n",ans);
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int l,m,x,y,ans=-1,flag=0; //flag是有嫌疑的段数,ans是有嫌疑的段左边的位置
boolean[] life=new boolean[1005]; //life为false代表有嫌疑
l=cin.nextInt();
m=cin.nextInt();
while(m>0){
m--;
x=cin.nextInt();
y=cin.nextInt();
for(int i=x;i<y;i++)
life[i]=true;
}
for(int i=0;i<l;i++){
if(!life[i]){
ans=i;
flag++;
}
}
if(flag>1)
System.out.println("No response!");
else
System.out.println(ans);
}
}
这题其实是一道难度偏高的题,但是有很多同学去进行了尝试。
ps:首页提示的第五条就是“题目难度与顺序无关”。
先解释一下题目中的“密码”。
密码=满足(由N位数字组成,且每连续M个数字之和都是质数)这一条件的数字串个数。以N=5,M=2为例,数字串应该满足:1.由5位数字组成;2.每连续2位数字的和是质数。即:第1位+第2位,第2位+第3位,第3位+第4位,第4位+第5位的和都是质数。
大部分过题的同学采取的是打表的方法,因为输入一共只有12*4=48种。
标程的解法是动态规划:
dp[i][j]表示只考虑前i位组成的满足每连续M位的和都是质数,并且最后M位组成的数字是j的数字串的个数。
那么我们枚举当前也就是第i+1位的数字k,可以知道加上第i+1位的k,新的数字串的结尾M个数字组成的数应该是(j*10)%(10^M)+k,所以dp[i+1][(j*10)%(10^M)+k]应该加上dp[i][j]这么多种情况。
怎么保证每连续M位的和都是质数呢?从i=M开始,我们每次都对最后M位进行审查,如果j的每个位子上的数的和不是质数,就让dp[i][j]=0。所以没清零的那些数字串,都可以保证每连续M位的和都是质数。
时间复杂度o(N*(10^M)*10),空间复杂度o(N*(10^M))。
//C++
#include<iostream>
#include<stdio.h>
using namespace std;
int n,m;
int m10; //m10=10^m
long long dp[15][10005]; //dp[i][j]表示只考虑前i位组成的满足每连续M位的和都是质数,并且最后M位组成的数字是j的数字串的个数
bool prime[105]; //prime[i]=1代表i是质数
int sum(int x) //求x各个位置上的数的和
{
int now=0;
for(int i=1;i<=m;i++)
{
now+=x%10;
x=x/10;
}
return now;
}
long long solve()
{
long long ans=0;
if(n<m)
return 0;
for(int i=0;i<=n;i++)
for(int j=0;j<m10;j++)
dp[i][j]=0;
dp[0][0]=1;
for(int i=1;i<=n;i++) //考虑前i个数字
{
for(int j=0;j<m10;j++) //考虑前i-1位组成的数字串的末尾M位数字
{
for(int k=0;k<10;k++) //考虑当前位的数字
dp[i][(j*10)%m10+k]+=dp[i-1][j];
}
if(i>=m) //当i大于等于M时,清空不符合要求的数字串
{
for(int j=0;j<m10;j++)
{
if(!prime[sum(j)])
dp[i][j]=0;
}
}
}
for(int i=0;i<m10;i++) //计算答案
ans+=dp[n][i];
return ans;
}
int main()
{
for(int i=2;i<=36;i++) //最多4个9相加只有36,判断36以内的质数有哪些
{
bool flag=0;
for(int j=2;j<i;j++)
{
if(i%j==0)
{
flag=1;
}
}
if(flag==0)
prime[i]=1;
}
scanf("%d%d",&n,&m);
m10=1;
for(int i=1;i<=m;i++)
m10*=10; //求10的m次方
printf("%lld\n",solve());
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n,m;
n=cin.nextInt();
m=cin.nextInt();
long[][] dp=new long[15][10005]; //dp[i][j]表示只考虑前i位组成的满足每连续M位的和都是质数,并且最后M位组成的数字是j的数字串的个数
boolean[] prime=new boolean[105]; //prime[i]=1代表i是质数
int m10; //m10=10^m
m10=1;
for(int i=1;i<=m;i++)
m10*=10; //求10的m次方
for(int i=2;i<=36;i++){ //最多4个9相加只有36,判断36以内的质数有哪些
boolean flag=false;
for(int j=2;j<i;j++){
if(i%j==0){
flag=true;
}
}
if(flag==false)
prime[i]=true;
}
long ans=0;
if(n>=m){
for(int i=0;i<=n;i++)
for(int j=0;j<m10;j++)
dp[i][j]=0;
dp[0][0]=1;
for(int i=1;i<=n;i++){ //考虑前i个数字
for(int j=0;j<m10;j++){ //考虑前i-1位组成的数字串的末尾M位数字
for(int k=0;k<10;k++) //考虑当前位的数字
dp[i][(j*10)%m10+k]+=dp[i-1][j];
}
if(i>=m){ //当i大于等于M时,清空不符合要求的数字串
for(int j=0;j<m10;j++){
int now=0,temp=j; //now是j各个位置上的数的和
for(int tempi=1;tempi<=m;tempi++){
now+=temp%10;
temp=temp/10;
}
if(!prime[now])
dp[i][j]=0;
}
}
}
for(int i=0;i<m10;i++) //计算答案
ans+=dp[n][i];
}
System.out.println(ans);
}
}
设bi为1表示按下第i个开关,p(j,i)为1表示第i个开关能控制第j个灯,那么题目就变为,求对于每个j,(p[j,1]&b1)^((p[j,2]&b2))^...(p[j,M]&bM)=1的N个M元方程组成的线性方程组是否有解。其中^表示异或,&表示与。
其中,p[j,i]是一个N行M列的系数矩阵,它的增广矩阵是在右边加一列1。增广矩阵的秩如果和系数矩阵相同,则有解。剩下的就是矩阵求秩的问题了,标程用到的方法是高斯消元。标程写的丑,同学们可以去网上找高斯消元的代码看。
时间复杂度o(M*N*M),空间复杂度o(N*M)。
//C++
#include<iostream>
#include<stdio.h>
using namespace std;
bool mat[105][105]; //矩阵
bool gg(int x,int y) //判断第x行的前y个数字是不是都是0
{
for(int i=1;i<=y;i++)
{
if(mat[x][i])
return 0;
}
return 1;
}
int main()
{
int n,m,x,t;
bool flag=0,temp;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) //根据输入生成系数矩阵
{
scanf("%d",&x);
while(x--)
{
scanf("%d",&t);
mat[t][i]=1;
}
}
for(int i=1;i<=n;i++) //变系数矩阵为增广矩阵
mat[i][m+1]=1;
for(int i=1;i<=m;i++) //高斯消元
{
for(int j=1;j<=n;j++)
{
if(mat[j][i] && gg(j,i-1))
{
for(int k=1;k<=n;k++)
{
if(k!=j && mat[k][i])
{
for(int g=i;g<=m+1;g++)
mat[k][g]^=mat[j][g];
}
}
break;
}
}
}
for(int i=1;i<=n;i++) //判断系数矩阵和增广矩阵的秩是否相同
{
temp=0;
for(int j=1;j<=m;j++)
{
if(mat[i][j])
{
temp=1;
break;
}
}
if(!temp && mat[i][m+1])
{
flag=1;
break;
}
}
if(!flag)
printf("YES\n");
else
printf("NO\n");
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
boolean[][] mat=new boolean[105][105]; //矩阵
int n,m,x,t;
boolean flag=false,temp;
n=cin.nextInt();
m=cin.nextInt();
for(int i=1;i<=m;i++){ //根据输入生成系数矩阵
x=cin.nextInt();
while(x>0){
x--;
t=cin.nextInt();
mat[t][i]=true;
}
}
for(int i=1;i<=n;i++) //变系数矩阵为增广矩阵
mat[i][m+1]=true;
for(int i=1;i<=m;i++){ //高斯消元
for(int j=1;j<=n;j++){
boolean gg=true; //gg表示第j行的前i-1个数是不是都是0
for(int tempi=1;tempi<=i-1;tempi++){
if(mat[j][tempi])
gg=false;
}
if(mat[j][i] && gg){
for(int k=1;k<=n;k++){
if(k!=j && mat[k][i]){
for(int g=i;g<=m+1;g++)
mat[k][g]^=mat[j][g];
}
}
break;
}
}
}
for(int i=1;i<=n;i++){ //判断系数矩阵和增广矩阵的秩是否相同
temp=false;
for(int j=1;j<=m;j++){
if(mat[i][j]){
temp=true;
break;
}
}
if(!temp && mat[i][m+1]){
flag=true;
break;
}
}
if(!flag)
System.out.println("YES");
else
System.out.println("NO");
}
}
题意抽象出来,其实就是做一个支持插队功能的队列。(插队是万恶之源。。。没有插队这题太简单了)实现插队功能我们很容易想到链表。所以我们用链表做一个队列。还剩下最后一个问题,怎么查找插队的位置呢?如果按照链表查找某个节点的方法,从头一个一个查的话,时间和链表长度成正比,而插队次数又很可能是和变动数一个级别的,这会导致超时。
所以我们把链表的地址和同学的编号绑定起来,即x号同学就放在地址x,这样我们就可以根据编号查询插队位置。所以我们的链表的next指针本质上是维护后面那个同学的编号。
为了实现排队功能,我们还需要记录队尾那个人的序号。同样为了实现打饭功能,我们要记录队首那个人的序号。
至于查询同学状态,我们在一开始将所有的同学设置成“coming”,在同学排队或者插队的时候把他的状态改为“waiting”,在他打饭的时候把他的状态设置成“eating”就可以了。
时间复杂度o(变动数),空间复杂度o(编号范围)。
//C++
#include<iostream>
#include<stdio.h>
using namespace std;
int nex[500005]; //相当于next指针
int status[500005]; //记录状态,0表示coming,1表示waiting,2表示eating
char s[6];
int main()
{
int n,x,y,tail; //tail记录队尾同学的编号,为0表示队伍为空
scanf("%d",&n);
tail=0;
while(n--)
{
scanf("%s",s);
if(s[0]=='p')
{
scanf("%d",&x);
status[x]=1;
nex[tail]=x;
tail=x;
}
if(s[0]=='d')
{
x=nex[0];
status[x]=2;
nex[0]=nex[x];
if(tail==x) //如果队伍里只剩一个人,此时要把队伍排空,要更改tail
tail=nex[x];
}
if(s[0]=='c')
{
scanf("%d %d",&x,&y);
status[x]=1;
nex[x]=nex[y];
nex[y]=x;
if(tail==y) //如果y是原本队伍的最后一个,此时x就变成队伍最后了,要更改tail
tail=nex[tail];
}
if(s[0]=='x')
{
scanf("%d",&x);
if(status[x]==0)
printf("coming\n");
if(status[x]==1)
printf("waiting\n");
if(status[x]==2)
printf("eating\n");
}
}
return 0;
}
//Java
import java.util.*;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
int[] nex=new int[500005]; //相当于next指针
int[] status=new int[500005]; //记录状态,0表示coming,1表示waiting,2表示eating
String s;
int n,x,y,tail; //tail记录队尾同学的编号,为0表示队伍为空
n=in.nextInt();
tail=0;
while(n!=0){
n--;
s=in.next();
if(s.equals("pd")){
x=in.nextInt();
status[x]=1;
nex[tail]=x;
tail=x;
}
if(s.equals("df")){
x=nex[0];
status[x]=2;
nex[0]=nex[x];
if(tail==x) //如果队伍里只剩一个人,此时要把队伍排空,要更改tail
tail=nex[x];
}
if(s.equals("cd")){
x=in.nextInt();
y=in.nextInt();
status[x]=1;
nex[x]=nex[y];
nex[y]=x;
if(tail==y) //如果y是原本队伍的最后一个,此时x就变成队伍最后了,要更改tail
tail=nex[tail];
}
if(s.equals("xw")){
x=in.nextInt();
if(status[x]==0)
System.out.println("coming");
if(status[x]==1)
System.out.println("waiting");
if(status[x]==2)
System.out.println("eating");
}
}
}
//java的输入太慢,对于这道题而言需要加速
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
本题难度也偏高。
队伍一共有三种:一大佬一端茶一倒水/两大佬一端茶(倒水)/三大佬。
为了最大化队伍的数量,优先组成第一种队伍,再考虑第二种队伍,最后剩下的大佬每三个人组成一个队伍。
于是问题转化为,最多能同时组成多少对一个端茶一个倒水的双人组,并且每组的两个人都不冲突。
我们可以借助二分图匹配的模型,考虑在任意一对个不冲突且一端茶一倒水的组合之间连一条边,然后求最大匹配。
最后根据最大匹配的数量、多余的端茶(倒水)的人的数量、和多余大佬的数量算出答案。
时间复杂度o(N^3),空间复杂度o(N^2)。
//C++
#include<iostream>
#include<stdio.h>
using namespace std;
char s[305][5]; //记录每个人的属性
bool ok[305][305]; //记录两个人是否冲突的邻接矩阵
int root[305];
int n;
bool life[305];
bool solve(int x) //找增广路函数
{
life[x]=1;
for(int i=1;i<=n;i++)
{
if(s[i][1]=='S' && ok[x][i]==0) //判断两人是否一个端茶一个倒水并且没冲突
{
if(life[i])
continue;
else
life[i]=1;
if(!root[i] || solve(root[i]))
{
root[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int m,u,v;
int numdl=0,numdc=0,numds=0,ans=0; //numdl是大佬数量,numdc是端茶同学数量,numds是倒水数量,ans是一个端茶一个倒水而且不冲突的双人组的最大数量
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",s[i]);
for(int i=1;i<=m;i++) //根据输入得到邻接矩阵
{
scanf("%d%d",&u,&v);
ok[u][v]=1;
ok[v][u]=1;
}
for(int i=1;i<=n;i++) //统计每种选手的数量
{
if(s[i][1]=='C')
numdc++;
if(s[i][1]=='L')
numdl++;
if(s[i][1]=='S')
numds++;
}
for(int i=1;i<=n;i++) //二分图匹配
{
for(int j=1;j<=n;j++)
life[j]=0;
if(s[i][1]=='C' && solve(i))
ans++;
}
if(ans>=numdl) //计算答案
printf("%d\n",numdl);
else
{
if((numdl-ans)/2>=(numdc+numds-ans*2))
printf("%d\n",numdc+numds-ans+(numdl-ans-(numdc+numds-ans*2)*2)/3);
else
printf("%d\n",ans+(numdl-ans)/2);
}
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
static String[] s=new String[305]; //记录每个人的属性
static boolean[][] ok=new boolean[305][305]; //记录两个人是否冲突的邻接矩阵
static int[] root=new int[305];
static int n;
static boolean[] life=new boolean[305];
static boolean solve(int x){ //找增广路函数
life[x]=true;
for(int i=1;i<=n;i++){
if(s[i].equals("DS") && ok[x][i]==false){ //判断两人是否一个端茶一个倒水并且没冲突
if(life[i])
continue;
else
life[i]=true;
if(root[i]==0 || solve(root[i])){
root[i]=x;
return true;
}
}
}
return false;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int m,u,v;
int numdl=0,numdc=0,numds=0,ans=0; //numdl是大佬数量,numdc是端茶同学数量,numds是倒水数量,ans是一个端茶一个倒水而且不冲突的双人组的最大数量
n=cin.nextInt();
m=cin.nextInt();
for(int i=1;i<=n;i++)
s[i]=cin.next();
for(int i=1;i<=m;i++){ //根据输入得到邻接矩阵
u=cin.nextInt();
v=cin.nextInt();
ok[u][v]=true;
ok[v][u]=true;
}
for(int i=1;i<=n;i++){ //统计每种选手的数量
if(s[i].equals("DC"))
numdc++;
if(s[i].equals("DL"))
numdl++;
if(s[i].equals("DS"))
numds++;
}
for(int i=1;i<=n;i++){ //二分图匹配
for(int j=1;j<=n;j++)
life[j]=false;
if(s[i].equals("DC") && solve(i))
ans++;
}
if(ans>=numdl) //计算答案
System.out.println(numdl);
else{
if((numdl-ans)/2>=(numdc+numds-ans*2))
System.out.println(numdc+numds-ans+(numdl-ans-(numdc+numds-ans*2)*2)/3);
else
System.out.println(ans+(numdl-ans)/2);
}
}
}
这个题的第一个难点在于h:m格式的输入,解决方法有很多,在这里不展开说,标程提供了一种方法。第二个难点在于没有给数据行数的情况下如何判断输入结束,C/C++的同学可以使用EOF机制解决这个问题,1000题就用到了这个机制,同学们可以去FAQ中查看参考代码。
题目实际上是要求我们把记录按照学号分类,同一个学号下的记录再按时间排序,检查每个人的记录1和纪录2、记录3和纪录4、记录5和记录6...是否有满足前一条记录在7:20之前(包括7:20),后一条记录在7:40之后(包括7:40)的情况,如果有,那么答案加上这个人。
我们可以把按照记录时间排序,然后处理每一条记录,考虑对应学号的上一条记录是奇数条还是偶数条,如果是奇数条,判断上一条的时间和这一条的时间是不是满足条件,满足则更新答案,同时更新当前学号记录条数的奇偶性和最后一条记录时间。因为学号有10位数字,开不了那么大的数组,但是学号种类最多只会等于记录条数,所以我们要对学号进行离散化,标程给出的是用map进行的方式。
另一种做法是在排序的时候,优先考虑对学号进行排序,学号相同再考虑时间,这样可以保证学号相同的记录都连在一起,处理答案的时候判断一下即可。
本题对排序的时间复杂度要求不超过记录条数*log(记录条数)。所以冒泡、选择等排序方法的性能是达不到要求的。标程给的是调用系统库的sort()函数。
时间复杂度o(记录条数*log(记录条数)),空间复杂度o(记录条数)。
//C++
#include<iostream>
#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;
struct Node
{
int t; //时间,h:m把转化成h*60+m储存
long long s; //学号
bool friend operator <(Node x1,Node x2) //定义Node结构体的大小比较为时间小的在前
{
return x1.t<x2.t;
}
}rec[100005]; //记录
map <long long,int> mp; //储存每个学号的上一次记录时间,为0说明上一次记录是偶数次
int main()
{
int ans=0,hh,mm; //ans为符合条件的人数
int l=7*60+20,r=7*60+40; //l对应7:20,r对应7:40
int n=0;
while(~scanf("%d:%d",&hh,&mm))
{
rec[n].t=hh*60+mm;
scanf("%lld",&rec[n].s);
n++;
}
sort(rec,rec+n); //把记录排序
for(int i=0;i<n;i++)
{
if(mp[rec[i].s]) //如果不为0说明上次是奇数次
{
if(rec[i].t>=r && mp[rec[i].s]<=l) //判断是否满足条件
ans++;
mp[rec[i].s]=0;
}
else
mp[rec[i].s]=rec[i].t;
}
printf("%d\n",ans);
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
static class Node implements Comparable<Node>{
public int t; //时间,h:m把转化成h*60+m储存
public long s; //学号
Node(){
t=0;
s=0;
}
public int compareTo(Node o){ //定义Node结构体的大小比较为优先考虑学号小的在前,学号相同情况下时间小的在前
if(s==o.s){
if(t==o.t)
return 0;
else{
if(t<o.t)
return -1;
else
return 1;
}
}
else{
if(s<o.s)
return -1;
else
return 1;
}
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
long[] s=new long[100005];
int[] h=new int[100005];
int[] m=new int[100005];
String c;
int n=0;
while(cin.hasNext()){
c=cin.next();
if(c.charAt(1)==':'){
h[n]=(c.charAt(0)-'0');
if(c.length()==4)
m[n]=(c.charAt(2)-'0')*10+(c.charAt(3)-'0');
else
m[n]=(c.charAt(2)-'0');
}
else{
h[n]=(c.charAt(0)-'0')*10+(c.charAt(1)-'0');
if(c.length()==5)
m[n]=(c.charAt(3)-'0')*10+(c.charAt(4)-'0');
else
m[n]=(c.charAt(3)-'0');
}
s[n]=cin.nextLong();
n++;
}
Node[] rec=new Node[n]; //记录
for(int i=0;i<n;i++){
rec[i]=new Node();
rec[i].t=h[i]*60+m[i];
rec[i].s=s[i];
}
Arrays.sort(rec); //把记录排序
int ans=0; //ans为符合条件的人数
int nextt; //上次记录时间
int l=7*60+20,r=7*60+40; //l对应7:20,r对应7:40
long nexts; //上次记录学号
nextt=0;
nexts=-1;
for(int i=0;i<n;i++){
if(nexts==rec[i].s && nextt!=0){ //说明上次是同一个人的奇数次记录
if(nextt<=l && rec[i].t>=r) //判断是否满足条件
ans++;
nextt=0;
}
else{
nextt=rec[i].t;
nexts=rec[i].s;
}
}
System.out.println(ans);
}
}
先向4.14惨案、4.15惨案中遇难的同学们表示哀悼。
如果没有断网时间的限制,这道题其实就是一个深度优先搜索(dfs)或广度优先搜索(bfs)从u出发能不能到达v的问题。加上断网时间之后,我们只需要在考虑两个楼栋是否连接的时候,把当前时间和断网时间考虑进去。注意:和i楼栋有关的网络全部失效意味着,如果消息要从楼栋a到楼栋b,不仅当前时间+1要小于等于楼栋b的断网时间,还要小于楼栋a的断网时间。
因为网是从某个时间之后开始断的,所以对于到达同一栋楼的方案,时间越早越好。所以推荐使用bfs。
时间复杂度o(N+M),空间复杂度o(N+M)。
//C++
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
int t[1005]; //断网时间
int life[1005]; //到达该楼栋的时间,-1表示没到达
bool ok[1005][1005]; //两个楼栋是否直接相连
queue <int> q;
int main()
{
int n,m,u,v,x;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
life[i]=-1; //初始状态都为没到达
scanf("%d",&t[i]); //得到断网时间
}
while(m--) //得到邻接矩阵
{
scanf("%d%d",&u,&v);
ok[u][v]=ok[v][u]=1;
}
scanf("%d%d",&u,&v); //这里开始,u表示起点,v表示终点
life[u]=0;
q.push(u);
while(q.size()) //bfs
{
x=q.front();
q.pop();
for(int i=1;i<=n;i++)
{
if(ok[x][i] && life[x]+1<=t[i] && life[x]+1<=t[x] && life[i]==-1) //判断x能不能到i,包括断网的情况也要考虑
{
life[i]=life[x]+1;
q.push(i);
}
}
}
if(life[v]==-1)
printf("GG\n");
else
printf("Nice!\n");
return 0;
}
//Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int[] t=new int[1005]; //断网时间
int[] life=new int[1005]; //到达该楼栋的时间,-1表示没到达
boolean[][] ok=new boolean[1005][1005]; //两个楼栋是否直接相连
int[] q=new int[1005]; //q是用数组实现的队列
int head=0,tail=0; //head是队列的头指针,tail是队列的尾指针
int n,m,u,v,x;
n=cin.nextInt();
m=cin.nextInt();
for(int i=1;i<=n;i++){
life[i]=-1; //初始状态都为没到达
t[i]=cin.nextInt(); //得到断网时间
}
while(m>0){ //得到邻接矩阵
m--;
u=cin.nextInt();
v=cin.nextInt();
ok[u][v]=ok[v][u]=true;
}
u=cin.nextInt();
v=cin.nextInt();//这里开始,u表示起点,v表示终点
life[u]=0;
q[tail]=u;
tail++;
while(tail>head){ //bfs
x=q[head];
head++;
for(int i=1;i<=n;i++){
if(ok[x][i] && life[x]+1<=t[i] && life[x]+1<=t[x] && life[i]==-1){ //判断x能不能到i,包括断网的情况也要考虑
life[i]=life[x]+1;
q[tail]=i;
tail++;
}
}
}
if(life[v]==-1)
System.out.println("GG");
else
System.out.println("Nice!");
}
}