matrix_last_acm

matrix_last_acm_5

password 123

A http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97960#problem/A

题意：给国王生日可能区间【a，b】，死亡日期可能区间【c，d】，a《=b < c《=d，问国王可能最短寿命和最长寿命。

解法：min=c-b max=d-a

 1 //#define debug
 2 //#define txtout
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<cmath>
 7 #include<cctype>
 8 #include<ctime>
 9 #include<iostream>
10 #include<algorithm>
11 #include<vector>
12 #include<queue>
13 #include<stack>
14 #include<map>
15 #include<set>
16 #define mt(a,b) memset(a,b,sizeof(a))
17 using namespace std;
18 typedef long long LL;
19 const double eps=1e-8;
20 const double pi=acos(-1.0);
21 const int inf=0x3f3f3f3f;
22 const int M=1e5+10;
23 int main(){
24     #ifdef txtout
25     freopen("in.txt","r",stdin);
26     freopen("out.txt","w",stdout);
27     #endif
28     int a,b,c,d;
29     while(~scanf("%d%d%d%d",&a,&b,&c,&d),a|b|c|d){
30         printf("%d %d
",c-b,d-a);
31     }
32     return 0;
33 }

View Code

B http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97960#problem/B

题意：给16种颜色的rgb值，输入一个rgb，输出最接近的颜色，距离是欧几里得距离，多个距离相等输出靠前的。

解法：暴力测试。

 1 //#define debug
 2 //#define txtout
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<cmath>
 7 #include<cctype>
 8 #include<ctime>
 9 #include<iostream>
10 #include<algorithm>
11 #include<vector>
12 #include<queue>
13 #include<stack>
14 #include<map>
15 #include<set>
16 #define mt(a,b) memset(a,b,sizeof(a))
17 using namespace std;
18 typedef long long LL;
19 const double eps=1e-8;
20 const double pi=acos(-1.0);
21 const int inf=0x3f3f3f3f;
22 const int M=1e5+10;
23 char str[32][16]={"White","Silver","Gray","Black","Red","Maroon","Yellow","Olive","Lime","Green","Aqua","Teal","Blue","Navy","Fuchsia","Purple"};
24 int R[32]={255,192,128,0,255,128,255,128,0,0,0,0,0,0,255,128};
25 int G[32]={255,192,128,0,0,0,255,128,255,128,255,128,0,0,0,0};
26 int B[32]={255,192,128,0,0,0,0,0,0,0,255,128,255,128,255,128};
27 int r,g,b;
28 int Square(int x){
29     return x*x;
30 }
31 int Distance2(int R,int G,int B){
32     return Square(R-r)+Square(G-g)+Square(B-b);
33 }
34 int solve(){
35     int id=0;
36     int d=Distance2(R[0],G[0],B[0]);
37     for(int i=1;i<16;i++){
38         int td=Distance2(R[i],G[i],B[i]);
39         if(d>td){
40             d=td;
41             id=i;
42         }
43     }
44     return id;
45 }
46 int main(){
47     #ifdef txtout
48     freopen("in.txt","r",stdin);
49     freopen("out.txt","w",stdout);
50     #endif
51     while(~scanf("%d%d%d",&r,&g,&b),~r){
52         puts(str[solve()]);
53     }
54     return 0;
55 }

View Code

C http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97960#problem/C

题意：输入T个队伍，P个问题，S次提交，问哪段时间内同时满足4个条件，1每个队都过题，2没有队全过ak，3每个题都有人过，4没有题被所有人过。保证这种时间段只有一个。

解法：按照提交时间排序，然后暴力测试。

  1 //#define debug
  2 //#define txtout
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<cmath>
  7 #include<cctype>
  8 #include<ctime>
  9 #include<iostream>
 10 #include<algorithm>
 11 #include<vector>
 12 #include<queue>
 13 #include<stack>
 14 #include<map>
 15 #include<set>
 16 #define mt(a,b) memset(a,b,sizeof(a))
 17 using namespace std;
 18 typedef long long LL;
 19 const double eps=1e-8;
 20 const double pi=acos(-1.0);
 21 const int inf=0x3f3f3f3f;
 22 const int M=5e3+10;
 23 int T,P,S,start_id,end_id;
 24 struct Submission{
 25     int teamID,hour,minute,second,total;
 26     char problemID[4];
 27     bool result;
 28     friend bool operator <(const Submission &a,const Submission &b){
 29         return a.total<b.total;
 30     }
 31     void init(){
 32         total=hour*3600+minute*60+second;
 33     }
 34 }submission[M];
 35 bool accepted[160][32];
 36 void get_result(int id){
 37     char c;
 38     submission[id].result=false;
 39     while(true){
 40         c=getchar();
 41         if(c=='
') return ;
 42         if(c=='Y') submission[id].result=true;
 43     }
 44 }
 45 void init(){
 46     start_id=-1;
 47     end_id=-1;
 48     for(int i=0;i<S;i++){
 49         submission[i].init();
 50     }
 51     for(int i=1;i<=T;i++){
 52         for(int j=0;j<P;j++){
 53             accepted[i][j]=false;
 54         }
 55     }
 56 }
 57 bool solved_at_least_one(int teamID){
 58     for(int i=0;i<P;i++){
 59         if(accepted[teamID][i]) return true;
 60     }
 61     return false;
 62 }
 63 bool solved_all(int teamID){
 64     for(int i=0;i<P;i++){
 65         if(!accepted[teamID][i]) return false;
 66     }
 67     return true;
 68 }
 69 bool at_least_one_team(int problemID){
 70     for(int i=1;i<=T;i++){
 71         if(accepted[i][problemID]) return true;
 72     }
 73     return false;
 74 }
 75 bool solved_by_all(int problemID){
 76     for(int i=1;i<=T;i++){
 77         if(!accepted[i][problemID]) return false;
 78     }
 79     return true;
 80 }
 81 bool judge(){
 82     for(int i=1;i<=T;i++){
 83         if(solved_at_least_one(i)) continue;
 84         return false;
 85     }
 86     for(int i=1;i<=T;i++){
 87         if(solved_all(i)) return false;
 88     }
 89     for(int i=0;i<P;i++){
 90         if(at_least_one_team(i)) continue;
 91         return false;
 92     }
 93     for(int i=0;i<P;i++){
 94         if(solved_by_all(i)) return false;
 95     }
 96     return true;
 97 }
 98 void solve(){
 99     init();
100     sort(submission,submission+S);
101     for(int i=0;i<S;i++){
102         if(submission[i].result){
103             accepted[submission[i].teamID][submission[i].problemID[0]-'A']=true;
104         }
105         if(judge()){
106             if(start_id==-1) start_id=i;
107             end_id=i;
108         }
109         else{
110             if(start_id!=-1) return ;
111         }
112     }
113 }
114 void out(int id){
115     if(id<0||id>S-1){
116         printf("--:--:--");
117         return ;
118     }
119     printf("%02d:%02d:%02d",submission[id].hour,submission[id].minute,submission[id].second);
120 }
121 int main(){
122     #ifdef txtout
123     freopen("in.txt","r",stdin);
124     freopen("out.txt","w",stdout);
125     #endif
126     while(~scanf("%d%d%d",&T,&P,&S),T|P|S){
127         for(int i=0;i<S;i++){
128             scanf("%d%s%d:%d:%d",&submission[i].teamID,submission[i].problemID,&submission[i].hour,&submission[i].minute,&submission[i].second);
129             get_result(i);
130         }
131         solve();
132         out(start_id);
133         putchar(' ');
134         if(end_id!=-1) end_id++;
135         out(end_id);
136         putchar('
');
137     }
138     return 0;
139 }

View Code

D http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97960#problem/D

题意：输入n个电梯，输入每个电梯停m楼，输入m个楼的层号，从i楼到j楼花费时间是两者的距离。求从起点到终点最短时间。

解法：同一个电梯的任意两层楼建双向边，距离为绝对值，单元最短路。

spfa

  1 //#define debug
  2 //#define txtout
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<cmath>
  7 #include<cctype>
  8 #include<ctime>
  9 #include<iostream>
 10 #include<algorithm>
 11 #include<vector>
 12 #include<queue>
 13 #include<stack>
 14 #include<map>
 15 #include<set>
 16 #define mt(a,b) memset(a,b,sizeof(a))
 17 using namespace std;
 18 typedef long long LL;
 19 const double eps=1e-8;
 20 const double pi=acos(-1.0);
 21 const int inf=0x3f3f3f3f;
 22 const int M=2e2+10;
 23 int W[M][M];
 24 int n,s,t;
 25 struct Elevator {
 26     int m;
 27     int floor[M];
 28 } elevator[16];
 29 class Spfa { ///最短路快速算法O(E*k)(k~=2)
 30     typedef int typec;///边权的类型
 31     static const int ME=4e4+10;///边的个数
 32     static const int MV=2e2+10;///点的个数
 33     struct E {
 34         int v,next;
 35         typec w;
 36     } e[ME];
 37     int n,le,head[MV],inque[MV],pre[MV],i,u,v;
 38     typec dist[MV];
 39     bool used[MV];
 40     queue<int> q;
 41 public:
 42     void init(int tn) { ///传入点的个数
 43         n=tn;
 44         le=0;
 45         for(i=0; i<=n; i++) head[i]=-1;
 46     }
 47     void add(int u,int v,typec w) {
 48         e[le].v=v;
 49         e[le].w=w;
 50         e[le].next=head[u];
 51         head[u]=le++;
 52     }
 53     bool solve(int s) { ///传入起点,存在负环返回false
 54         for(i=0; i<=n; i++) {
 55             dist[i]=inf;
 56             used[i]=true;
 57             inque[i]=0;
 58             pre[i]=-1;
 59         }
 60         used[s]=false;
 61         dist[s]=0;
 62         inque[s]++;
 63         while(!q.empty()) q.pop();
 64         q.push(s);
 65         while(!q.empty()) {
 66             u=q.front();
 67             q.pop();
 68             used[u]=true;
 69             for(i=head[u]; ~i; i=e[i].next) {
 70                 v=e[i].v;
 71                 if(dist[v]>dist[u]+e[i].w) {
 72                     dist[v]=dist[u]+e[i].w;
 73                     pre[v]=u;
 74                     if(!used[v]) continue;
 75                     used[v]=false;
 76                     q.push(v);
 77                     inque[v]++;
 78                     if(inque[v]>n) return false;
 79                 }
 80             }
 81         }
 82         return true;
 83     }
 84     typec getdist(int id) {
 85         return dist[id];
 86     }
 87     int getpre(int id) {
 88         return pre[id];
 89     }
 90 } spfa;
 91 void add(int u,int v,int w) {
 92     if(W[u][v]>w) {
 93         W[u][v]=w;
 94         W[v][u]=w;
 95     }
 96 }
 97 void init() {
 98     mt(W,0x3f);
 99     for(int i=0; i<n; i++) {
100         int m=elevator[i].m;
101         for(int j=0; j<m; j++) {
102             for(int k=j+1; k<m; k++) {
103                 int u=elevator[i].floor[j];
104                 int v=elevator[i].floor[k];
105                 int w=abs(u-v);
106                 add(u,v,w);
107             }
108         }
109     }
110 }
111 int solve() {
112     init();
113     spfa.init(150);
114     for(int i=0;i<150;i++){
115         for(int j=0;j<150;j++){
116             if(W[i][j]==inf) continue;
117             spfa.add(i,j,W[i][j]);
118         }
119     }
120     spfa.solve(s);
121     return spfa.getdist(t);
122 }
123 int main() {
124 #ifdef txtout
125     freopen("in.txt","r",stdin);
126     freopen("out.txt","w",stdout);
127 #endif
128     while(~scanf("%d%d%d",&n,&s,&t),n|s|t) {
129         for(int i=0; i<n; i++) {
130             scanf("%d",&elevator[i].m);
131             for(int j=0; j<elevator[i].m; j++) {
132                 scanf("%d",&elevator[i].floor[j]);
133             }
134         }
135         printf("%d
",solve());
136     }
137     return 0;
138 }

View Code

priority——queue dij

  1 //#define debug
  2 //#define txtout
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<cmath>
  7 #include<cctype>
  8 #include<ctime>
  9 #include<iostream>
 10 #include<algorithm>
 11 #include<vector>
 12 #include<queue>
 13 #include<stack>
 14 #include<map>
 15 #include<set>
 16 #define mt(a,b) memset(a,b,sizeof(a))
 17 using namespace std;
 18 typedef long long LL;
 19 const double eps=1e-8;
 20 const double pi=acos(-1.0);
 21 const int inf=0x3f3f3f3f;
 22 const int M=2e2+10;
 23 int W[M][M];
 24 int n,s,t;
 25 struct Elevator {
 26     int m;
 27     int floor[M];
 28 } elevator[16];
 29 class Dijkstra { ///Dijkstra 堆优化O(E*log(V))
 30     typedef int typec;///边权的类型
 31     static const int ME=4e4+10;///边的个数
 32     static const int MV=2e2+10;///点的个数
 33     struct Q {
 34         int id;
 35         typec w;
 36         friend bool operator <(const Q &a,const Q &b) {
 37             return a.w>b.w;
 38         }
 39     } now;
 40     priority_queue<Q> q;
 41     struct E {
 42         int v,next;
 43         typec w;
 44     } e[ME];
 45     int n,le,head[MV],pre[MV],u,v,i;
 46     typec dist[MV],w;
 47     bool used[MV];
 48 public:
 49     void init(int tn) {///传入点的个数
 50         n=tn;
 51         le=0;
 52         for(i=0; i<=n; i++) head[i]=-1;
 53     }
 54     void add(int u,int v,typec w) {
 55         e[le].v=v;
 56         e[le].w=w;
 57         e[le].next=head[u];
 58         head[u]=le++;
 59     }
 60     void solve(int s) {///传入起点
 61         for(i=0; i<=n; i++) {
 62             used[i]=true;
 63             dist[i]=inf;
 64             pre[i]=-1;
 65         }
 66         dist[s]=0;
 67         now.id=s;
 68         now.w=0;
 69         while(!q.empty()) q.pop();
 70         q.push(now);
 71         while(!q.empty()) {
 72             now=q.top();
 73             q.pop();
 74             u=now.id;
 75             if(!used[u]) continue;
 76             used[u]=false;
 77             for(i=head[u]; ~i; i=e[i].next) {
 78                 v=e[i].v;
 79                 w=e[i].w;
 80                 if(used[v]&&dist[v]>w+dist[u]) {
 81                     dist[v]=w+dist[u];
 82                     pre[v]=u;
 83                     now.id=v;
 84                     now.w=dist[v];
 85                     q.push(now);
 86                 }
 87             }
 88         }
 89     }
 90     typec getdist(int id) {
 91         return dist[id];
 92     }
 93     int getpre(int id) {
 94         return pre[id];
 95     }
 96 } spfa;
 97 void add(int u,int v,int w) {
 98     if(W[u][v]>w) {
 99         W[u][v]=w;
100         W[v][u]=w;
101     }
102 }
103 void init() {
104     mt(W,0x3f);
105     for(int i=0; i<n; i++) {
106         int m=elevator[i].m;
107         for(int j=0; j<m; j++) {
108             for(int k=j+1; k<m; k++) {
109                 int u=elevator[i].floor[j];
110                 int v=elevator[i].floor[k];
111                 int w=abs(u-v);
112                 add(u,v,w);
113             }
114         }
115     }
116 }
117 int solve() {
118     init();
119     spfa.init(150);
120     for(int i=0; i<150; i++) {
121         for(int j=0; j<150; j++) {
122             if(W[i][j]==inf) continue;
123             spfa.add(i,j,W[i][j]);
124         }
125     }
126     spfa.solve(s);
127     return spfa.getdist(t);
128 }
129 int main() {
130 #ifdef txtout
131     freopen("in.txt","r",stdin);
132     freopen("out.txt","w",stdout);
133 #endif
134     while(~scanf("%d%d%d",&n,&s,&t),n|s|t) {
135         for(int i=0; i<n; i++) {
136             scanf("%d",&elevator[i].m);
137             for(int j=0; j<elevator[i].m; j++) {
138                 scanf("%d",&elevator[i].floor[j]);
139             }
140         }
141         printf("%d
",solve());
142     }
143     return 0;
144 }

View Code

F http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97960#problem/F

题意：输入一些时间，有正有负，最后输出他们的和。

解法：把字符串的整数处理出来累加。

 1 //#define debug
 2 //#define txtout
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<cmath>
 7 #include<cctype>
 8 #include<ctime>
 9 #include<iostream>
10 #include<algorithm>
11 #include<vector>
12 #include<queue>
13 #include<stack>
14 #include<map>
15 #include<set>
16 #define mt(a,b) memset(a,b,sizeof(a))
17 using namespace std;
18 typedef long long LL;
19 const double eps=1e-8;
20 const double pi=acos(-1.0);
21 const int inf=0x3f3f3f3f;
22 const int M=1e2+10;
23 char a[M];
24 int solve(){
25     int sign=1;
26     if(a[0]=='-') sign=-1;
27     int i;
28     int hour=0;
29     for(i=1;a[i];i++){
30         if(!isdigit(a[i])) break;
31         hour*=10;
32         hour+=a[i]-'0';
33     }
34     int minute=0;
35     i++;
36     for(;a[i];i++){
37         minute*=10;
38         minute+=a[i]-'0';
39     }
40     return (hour*60+minute)*sign;
41 }
42 int main(){
43     #ifdef txtout
44     freopen("in.txt","r",stdin);
45     freopen("out.txt","w",stdout);
46     #endif
47     int sum=0;
48     while(~scanf("%s",a)){
49         if(a[0]=='$'||a[0]=='#'){
50             printf("%d:%02d
",sum/60,sum%60);
51             sum=0;
52             continue;
53         }
54         sum+=solve();
55     }
56     return 0;
57 }

View Code

G http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97960#problem/G

题意：n个城市，m条无向边，k条龙，给出图，和龙所在城市c，初始脑袋的个数s，每分钟增加的脑袋数n。每个勇士每分钟可以砍一个龙头或者走到一个相邻的城市。可以决定勇士一开始的位置。问最少几个勇士可以杀死所有的龙。

解法：如果龙的每分钟增加n小于勇士的总数，那总有一天能杀完这些龙，如果n》=勇士的总数，那必须在第一天将s全砍了。最后答案是每个连通块需要的勇士相加，对每个连通块可以二分勇士数量，验证时判断n》=总数的龙的s求和是否小于等于mid。

  1 //#define debug
  2 //#define txtout
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<cmath>
  7 #include<cctype>
  8 #include<ctime>
  9 #include<iostream>
 10 #include<algorithm>
 11 #include<vector>
 12 #include<queue>
 13 #include<stack>
 14 #include<map>
 15 #include<set>
 16 #define mt(a,b) memset(a,b,sizeof(a))
 17 using namespace std;
 18 typedef long long LL;
 19 const double eps=1e-8;
 20 const double pi=acos(-1.0);
 21 const int inf=0x3f3f3f3f;
 22 const int M=1e3+10;
 23 struct E{
 24     int u,v;
 25 }e[M*M];
 26 struct Dragon{
 27     int c,s,n;
 28 }dragon[M];
 29 vector<int> g[M],dragon_id;
 30 bool vis[M];
 31 int n,m,k;
 32 void add(int u,int v){
 33     g[u].push_back(v);
 34     g[v].push_back(u);
 35 }
 36 void init(){
 37     for(int i=1;i<=n;i++){
 38         g[i].clear();
 39         vis[i]=false;
 40     }
 41     for(int i=0;i<m;i++){
 42         add(e[i].u,e[i].v);
 43     }
 44 }
 45 bool judge(int mid){
 46     int len=dragon_id.size();
 47     int sum=0;
 48     for(int i=0;i<len;i++){
 49         if(dragon[dragon_id[i]].n<mid) continue;
 50         sum+=dragon[dragon_id[i]].s;
 51     }
 52     return sum<=mid;
 53 }
 54 int get_cost(){
 55     int len=dragon_id.size();
 56     int L=1,R=0;
 57     for(int i=0;i<len;i++){
 58         R=max(R,dragon[dragon_id[i]].n+1);
 59     }
 60     int result=R;
 61     while(L<=R){
 62         int mid=(L+R)>>1;
 63         if(judge(mid)){
 64             result=mid;
 65             R=mid-1;
 66         }
 67         else{
 68             L=mid+1;
 69         }
 70     }
 71     return result;
 72 }
 73 void dfs(int u){
 74     vis[u]=true;
 75     for(int i=0;i<k;i++){
 76         if(dragon[i].c==u) dragon_id.push_back(i);
 77     }
 78     int len=g[u].size();
 79     for(int i=0;i<len;i++){
 80         int v=g[u][i];
 81         if(vis[v]) continue;
 82         dfs(v);
 83     }
 84 }
 85 int solve(){
 86     init();
 87     int result=0;
 88     for(int i=1;i<=n;i++){
 89         if(vis[i]) continue;
 90         dragon_id.clear();
 91         dfs(i);
 92         result+=get_cost();
 93     }
 94     return result;
 95 }
 96 int main(){
 97     #ifdef txtout
 98     freopen("in.txt","r",stdin);
 99     freopen("out.txt","w",stdout);
100     #endif
101     while(~scanf("%d%d%d",&n,&m,&k),n|m|k){
102         for(int i=0;i<m;i++){
103             scanf("%d%d",&e[i].u,&e[i].v);
104         }
105         for(int i=0;i<k;i++){
106             scanf("%d%d%d",&dragon[i].c,&dragon[i].s,&dragon[i].n);
107         }
108         printf("%d
",solve());
109     }
110     return 0;
111 }

View Code

end