# Part of GCPC2017 Problem Solution

C joyride

It's another sunny day in July. You decide to spend time with your daughter joy, because she likes fairy Park in the next town very much. You plan to stay there for one day. Your wife (unfortunately she has to work) agrees to drive you to the park and pick you up. Oh dear! She's very tight with time, so she tells you the exact time when she'll arrive at the entrance to the park, and you'll have to be right there at that point. You also know that you don't want to wait outside, because it will make your daughter sad: she could have stayed in the park more! Now you have to plan your trip to the park. You know when you're coming and when you have to leave. The park contains several recreational facilities, and there are some trails connecting them. There are no tickets in the park, but it costs money to play a project. Because this is joy's favorite park, you already know how long it will take for each amusement facility to finish and how many tickets it will take. When you walk through the park, it's obvious that you can't skip the rides you pass because it makes joy unhappy. Because joy likes the park very much, she is happy to play with an amusement facility many times. Traveling between two facilities can also take some time. Because you are a farsighted parent and you want to spend as little money as possible in the park, can you figure out how many tickets must be spent?

Through the analysis of the theme map, we can conclude that there are two different schemes for each kind of amusement facility: playing once to play next or playing multiple times. Then two schemes can be extended naturally: memory search and shortest path of hierarchical graph.

How to understand memory search to solve this problem?

It can be assumed that the first dimension of the dp array is the location, the second dimension is the time spent, and the final state is the location 1, and the time spent is remaining. Then the whole graph is traversed by dfs, and each node is divided into two different schemes.

1. Continue to search along the graph
2. Repeat recursion of the current point

Finally, the answer to this question is to add all the recursive sub-answers to the initial state.

```import java.math.*;
import java.io.*;
import java.text.*;
import java.util.*;
public class Main
{
static int connections[][]=new int;
static int dp[][]=new int;
static int MoneyCost[]=new int;
static int TimeCost[]=new int;
static final int INF=1000000007;
static int ride,pavement,cost;
public static int dfs(int CurrentLoc,int CurrentTime,int Tlimit,int Rlimit)
{
if(CurrentTime>Tlimit)
return INF;
else if(CurrentLoc==1&&CurrentTime==Tlimit)This is the initial state.
return 0;
else if(dp[CurrentLoc][CurrentTime]!=-1)
return dp[CurrentLoc][CurrentTime];
else
{
dp[CurrentLoc][CurrentTime]=INF;
for(int i=1;i<=Rlimit;i++)
{
if(connections[CurrentLoc][i]>0)
{
dp[CurrentLoc][CurrentTime]=
Math.min(dp[CurrentLoc][CurrentTime],dfs(i,CurrentTime+cost+TimeCost[i],Tlimit,Rlimit)+MoneyCost[i]);
}
}
dp[CurrentLoc][CurrentTime]=
Math.min(dp[CurrentLoc][CurrentTime],dfs(CurrentLoc, CurrentTime+TimeCost[CurrentLoc],Tlimit, Rlimit)+MoneyCost[CurrentLoc]);
return dp[CurrentLoc][CurrentTime];
}
}
public static void main(String args[])throws IOException
{
int remaining=Integer.parseInt(tmp);
String tmps[]=tmp.trim().split(" ");
ride=Integer.parseInt(tmps);pavement=Integer.parseInt(tmps);cost=Integer.parseInt(tmps);
for(int i=1,tmp3,tmp4;i<=pavement+ride;i++)
{
String tmps2[]=tmp.trim().split(" ");
tmp3=Integer.parseInt(tmps2);tmp4=Integer.parseInt(tmps2);
if(i<=pavement)
{
connections[tmp3][tmp4]=1;
connections[tmp4][tmp3]=1;
}
else
{
TimeCost[i-pavement]=tmp3;
MoneyCost[i-pavement]=tmp4;
}
}
for(int i=0;i<=1250;i++)
for(int j=0;j<=1250;j++)
dp[i][j]=-1;
int ans=dfs(1,TimeCost,remaining,ride)+MoneyCost;
if(ans>=INF)
System.out.println("It is a trap.");
else
System.out.println(ans);
bf.close();
}
}```

If the shortest path of hierarchical graph is used, the idea is similar to the memory search mentioned above. A two-dimensional array is used to store the results of different locations and different times.

```import java.math.*;
import java.io.*;
import java.text.*;
import java.util.*;

import sun.misc.ObjectInputFilter.Status;
public class Main
{
public static class Node
{
int next,to;
public Node(int a,int b)
{
this.next=a;
this.to=b;
}
}
public static class Status
{
int CurTime,CurLoc;
public Status(int a,int b)
{
this.CurTime=b;
this.CurLoc=a;
}
}
static final int INF=1000000007;
static Node nodes[]=new Node;
static int MoneyCost[]=new int;
static int TimeCost[]=new int;
static int distances[][]=new int;
static boolean inquiry[][]=new boolean;//Markup arrays also need to be open in two dimensions
static int cnt=0,remaining,ride,pavement,cross;
public static void construction(int from,int to)
{
}
public static void spfa(int threshold)
{
for(int i=0;i<=1230;i++)
for(int j=0;j<=1230;j++)
{
distances[i][j]=INF;
inquiry[i][j]=false;
}
inquiry[threshold][TimeCost]=true;
distances[threshold][TimeCost[threshold]]=MoneyCost;
Status tmp6=new Status(threshold,TimeCost[threshold]);
while(q.isEmpty()==false)
{
Status cur=q.poll();
//System.out.println(cur.CurTime);
inquiry[cur.CurLoc][cur.CurTime]=false;
int nxttime=(cur.CurTime+TimeCost[cur.CurLoc]);
//System.out.println(cur.CurLoc+" "+nxttime+" "+remaining);
if(nxttime<=remaining)
{
if(distances[cur.CurLoc][cur.CurTime]+MoneyCost[cur.CurLoc]<distances[cur.CurLoc][nxttime])
{
distances[cur.CurLoc][nxttime]=distances[cur.CurLoc][cur.CurTime]+MoneyCost[cur.CurLoc];
if(inquiry[cur.CurLoc][nxttime]==false)
{
Status tmp7=new Status(cur.CurLoc,nxttime);
inquiry[cur.CurLoc][nxttime]=true;
}
}
}

{
int nxt=nodes[i].to;
int nxtTime=cur.CurTime+cross+TimeCost[nxt];
if(nxtTime>remaining)
continue;
else
{
if(distances[nxt][nxtTime]>distances[cur.CurLoc][cur.CurTime]+MoneyCost[nxt])
{
distances[nxt][nxtTime]=distances[cur.CurLoc][cur.CurTime]+MoneyCost[nxt];
if(!inquiry[nxt][nxtTime])
{
Status tmp9=new Status(nxt,nxtTime);
inquiry[nxt][nxtTime]=true;
}
}
}
}
}
}
public static void main(String args[])throws IOException
{
remaining=Integer.parseInt(tmp);
String tmps[]=tmp.trim().split(" ");
ride=Integer.parseInt(tmps);
pavement=Integer.parseInt(tmps);
cross=Integer.parseInt(tmps);
for(int i=1;i<=2500;i++)
for(int i=1,a,b;i<=pavement+ride;i++)
{
String tmps2[]=tmp.trim().split(" ");
a=Integer.parseInt(tmps2);b=Integer.parseInt(tmps2);
if(i>pavement)
{
TimeCost[i-pavement]=a;
MoneyCost[i-pavement]=b;
}
else
{
construction(a,b);
construction(b,a);
}
}
spfa(1);
// for(int i=1;i<=6;i++)
//     System.out.println(distances[i]);
if(distances[remaining]>=INF)
System.out.println("It is a trap.");
else
System.out.println(distances[remaining]);
bf.close();
}

}```

E plug it in!

Adam just moved into his new apartment and simply placed everything into it at random. This means in particular that he did not put any effort into placing his electronics in a way that each one can have its own electric socket.
Since the cables of his devices have limited reach, not every device can be plugged into every socket without moving it first. As he wants to use as many electronic devices as possible right away without moving stuff around, he now tries to figure out which device to plug into which socket. Luckily the previous owner left behind a plugbar which turns one electric socket into 3.
Can you help Adam figure out how many devices he can power in total?

Adam has just moved into his new apartment and put everything in a mess. This especially means that it does not organize all electronic devices into the case that each electronic device has plugs. Because the cable of this electronic device has power limitation, not every device can find its own socket. In his unwilling to toss about and want to find as many sockets as possible, he tries to find a solution which plug matches which interface. Fortunately, the landlord gave him an outlet, which allowed him to use one plug as three. Can you help Adam find the most number of appliances that can be connected to the circuit?

Typical bipartite graph matching, but this one is enhanced to match three points, so it is slightly different. As for how to achieve such a point when the three-purpose settings? If we enumerate the case of enlarging the capacity of each point by three times, it is very likely that the time-out will occur.

So a different way of thinking is not device matching plug, but plug matching device. When a plug is matched to three devices, the so-called triple expansion can be accomplished. As for the realization, we can directly match two more bipartite graphs for a certain point. (Since there are no more than two additional additions, jump out of the loop when the answer is updated to 2)

```import java.math.*;
import java.io.*;
import java.text.*;
import java.util.*;
public class Main
{
public static class Node
{
int next,to;
public Node(int a,int b)
{
this.next=a;
this.to=b;
}
}
static Node nodes[]=new Node;
static int cnt=0;
static int socket,device,connection;
public static void construction(int from,int to)
{
}
static int matches[]=new int;
static int secmatches[]=new int;
static boolean inquiry[]=new boolean;
public static Boolean Matching(int current)
{
{
int nxt=nodes[i].to;
if(inquiry[nxt]==false)
{
inquiry[nxt]=true;
if(matches[nxt]==0||Matching(matches[nxt])==true)
{
matches[nxt]=current;
return true;
}
}
}
return false;
}
public static void main(String args[])throws IOException
{
String tmps[]=tmp.trim().split(" ");
socket=Integer.parseInt(tmps);
device=Integer.parseInt(tmps);
connection=Integer.parseInt(tmps);
for(int i=1;i<=socket+device;i++)
for(int i=1,a,b;i<=connection;i++)
{
String tmps2[]=tmp.trim().split(" ");
a=Integer.parseInt(tmps2);
b=Integer.parseInt(tmps2);
construction(a,b);
}
long ans=0;
for(int i=1;i<=socket;i++)//One-to-one matching
{
for(int j=1;j<=device;j++)
inquiry[j]=false;
if(Matching(i)==true)
ans++;
}
for(int y=1;y<=device;y++)
secmatches[y]=matches[y];Duplicate matching results
//System.out.println(ans);
long finans=0,tmpans=0;
for(int i=1;i<=socket;i++)
{
for(int y=1;y<=device;y++)
matches[y]=secmatches[y];
tmpans=0;
for(int j=1;j<=2;j++)//Two more matches are made for a point.
{
for(int k=1;k<=device;k++)
inquiry[k]=false;
if(Matching(i)==true)
tmpans++;
}
finans=Math.max(finans,tmpans);
if(finans==2)
break;
}
System.out.println(finans+ans);
bf.close();
}
}```

I uberwatch

The seminar was over and the mission was completed. Even the annoying TA has no problem with your programming project. It's time to play a game! As always, procrastination is a good time for you: Cold Air has just released Uberwatch, a challenging first-person game. Unfortunately, you are not very good at such games. But uberwatch offers more than one game-based trick. In uberwatch, you can destroy all enemies by pressing a key to launch an infinite attack, but the disadvantage of this attack is that it has CD time. At the end of CD time, you can start skills at any time. Cooling immediately after skill use. With this little bit of knowledge, you can quickly come up with a magic trick: hide from the enemy until infinite attacks can be used, wait for the right time, repeat the above.

At the end of the game, your teammates all come to appreciate your tremendous contribution to the game you just played. But you want to know how many enemies can you get rid of with the best timing? This game can be seen as N periods of time, infinite attack at the beginning did not cool well, it takes M period to cool. The end of the first CD time is M+1 time period. If the infinite attack is used in the first time period, it immediately starts entering CD time and removes the CD again at the time of I+M.

There are obviously two different ways to deal with this problem:

The first is macro enumeration. Through the analysis, we can find that although the status of this topic is intermittent, on the whole, every state of using skills is transferred from the I-m state, so we can directly get the equation: DP [i] = max(DP[i-m],DP[i]).

The second is micro enumeration. That is to analyze the cooling time one by one, which is more cumbersome.

Let the first dimension be the time and the second dimension the cooling time. If the cooling time is analyzed, then the state transition equation will be DP[i][j]=max(dp[i][j],dp[i-1][j-1]), because there may be many different schemes to reach the state of dp[i][j], so when transferring the directly related state (when cooling the previous second). Also check the optimality.

Then it is to analyze the development of skills: fired or not fired.

If you fire, there will be such a state transition mode: dp[i]=max(dp[i],dp[i-1][interval]+enemies[i]), which means that the current state of firing and getting the number of enemies killed and the existing state is better than which.

If you do not fire, then there will be such a state transition mode: dp[i][interval]=max(dp[i][interval],dp[i-1][interval]), which is still better than the directly related state and the existing state.

```import java.math.*;
import java.io.*;
import java.text.*;
import java.util.*;
public class Main
{
static int enemies[]=new int;
static int dp[][]=new int;
public static void main(String args[])throws IOException
{
String tmps[]=tmp.trim().split(" ");
int n=Integer.parseInt(tmps),interval=Integer.parseInt(tmps);
String tmps2[]=tmp.trim().split(" ");
for(int i=1;i<=n;i++)
enemies[i]=Integer.parseInt(tmps2[i-1]);
for(int i=interval+1;i<=n;i++)
{
for(int j=1;j<=interval;j++)
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]);
dp[i][interval]=Math.max(dp[i][interval],dp[i-1][interval]);
dp[i]=Math.max(dp[i],dp[i-1][interval]+enemies[i]);
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=interval;j++)
ans=Math.max(dp[i][j],ans);
System.out.println(ans);
bf.close();
}

}```

C pants on fire

This problem belongs to closure transfer, and can be solved directly by improved floyd algorithm.

```import java.math.*;
import java.io.*;
import java.text.*;
import java.util.*;
public class Main
{
static int value[]=new int;
static int cnt=0;
static boolean dis[][]=new boolean;
static final int mod=19991126;
public static void floyd(int limit)
{
for(int k=1;k<=limit;k++)
for(int i=1;i<=limit;i++)
for(int j=1;j<=limit;j++)
{
dis[i][j]=(dis[i][j])||((dis[i][k])&&(dis[k][j]));
}
}
public static void main(String args[])throws IOException
{
String tmps[]=tmp.trim().split(" ");
int n=Integer.parseInt(tmps),m=Integer.parseInt(tmps);
cnt=0;
for(int i=1;i<=n;i++)
{
String tmps2[]=tmp.trim().split(" ");
int res1=((tmps2.hashCode()%mod+mod)%mod),res2=(tmps2.hashCode()%mod+mod)%mod;
if(value[res1]==0)
value[res1]=++cnt;
if(value[res2]==0)
value[res2]=++cnt;
dis[value[res1]][value[res2]]=true;
}
floyd(cnt);
for(int i=1;i<=m;i++)
{
String tmps3[]=tmp.trim().split(" ");
int res1=(tmps3.hashCode()%mod+mod)%mod,res2=(tmps3.hashCode()%mod+mod)%mod;
if(dis[value[res1]][value[res2]])
System.out.println("Fact");
else if(dis[value[res2]][value[res1]])
System.out.println("Alternative Fact");
else
System.out.println("Pants on Fire");
}
bf.close();
}
}```

Posted on Mon, 26 Aug 2019 06:57:21 -0700 by bolter