一开始几道题写到吐血,真的自己现在好弱 1011 水题不说了
#include<bits/stdc++.h> using namespace std; const int N = 105; typedef unsigned long long ll; const int MOD = 1e9+7; int c[5]; int main() { double ans = 1; for(int i = 1; i <= 3; ++i) { double mx = -1; for(int j = 1; j <= 3; ++j) { double a; scanf("%lf", &a); if(mx < a) { mx = a; c[i] = j; } } ans *= mx; } ans = (ans*0.65-1)*2; for(int i = 1; i <= 3; ++i) { printf("%s ", c[i]==1? "W": (c[i]==2?"T":"L") ); } printf("%.2f\n", ans); }1012 比较麻烦,一开始处理一下
#include<bits/stdc++.h> using namespace std; const int N = 105; typedef unsigned long long ll; const int MOD = 1e9+7; const int INF = 0x3f3f3f3f; int n, m; char s[2005][8]; int C[5][2005]; int cc[5][105]; map<string, int> cmp; map<int,int> mp; map<int,int> ::iterator it; int main() { while(~scanf("%d %d",&n,&m)) { memset(cc, 0, sizeof(cc)); cmp.clear(); for(int i = 1; i <= n; ++i) { scanf("%s %d %d %d", s[i], &C[0][i], &C[1][i], &C[2][i]); cmp[s[i]] = i; C[3][i] = (C[0][i]+C[1][i]+C[2][i]) / 3; //iprintf(" %d", C[3][i]); } int cnt = 1; for(int j = 0; j < 4; ++j) { mp.clear(); for(int i = 1; i <= n; ++i) { mp[C[j][i]] ++; } cnt = 1; for(it = mp.end(), --it; ; --it) { cc[j][it->first] = cnt; cnt += it->second; if(it == mp.begin()) break; } for(int i = 1; i <= n; ++i) { C[j][i] = cc[j][C[j][i]]; } } // for(int i = 1; i <= n; ++i) { // for(int j = 0; j < 4; ++j) printf("%d ", C[j][i]); printf("\n"); // } for(int i = 1; i <= m; ++i) { char tmp[15]; scanf("%s", tmp); if( cmp.find(tmp) == cmp.end() ) printf("N/A\n"); else { int tt = cmp[tmp]; int po, mi = INF; // for(int j = 0; j < 4; ++j) printf("%d ",C[j][tt]); printf("\n"); if(mi > C[3][tt]) { mi = C[3][tt]; po = 3; } for(int j = 0; j < 3; ++j) { if(mi > C[j][tt]) { mi = C[j][tt]; po = j; } } printf("%d ", mi); if(po == 0) printf("C\n"); else if(po == 1) printf("M\n"); else if(po == 2) printf("E\n"); else printf("A\n"); } } } return 0; }1013 dfs一下
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; const int MOD = 1e9+7; const int INF = 0x3f3f3f3f; const int N = 1e3+5; int n, m, k; struct Node{ int nx, to; }E[N*N*2]; int head[N], tot; void add(int fr,int to) { E[tot].to = to; E[tot].nx = head[fr]; head[fr] = tot++; } int ans[N]; int cnt; int nop; int vis[N]; void dfs(int x) { for(int i = head[x]; ~i; i = E[i].nx) { int to = E[i].to; if(!vis[to] && to != nop) { vis[to] = 1; dfs(to); } } } void solve(int x) { cnt = 0; memset(vis, 0, sizeof(vis)); nop = x; for(int i = 1; i <= n; ++i) { if(i != nop && !vis[i]) { dfs(i); cnt ++; } } ans[x] = cnt-1; } int main() { while(~scanf("%d %d %d", &n, &m, &k)) { memset(head, -1, sizeof(head)); tot = 0; memset(ans, -1, sizeof(ans)); for(int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); add(a, b); add(b, a); } for(int i = 1; i <= k; ++i) { int a; scanf("%d",&a); if(ans[a] == -1) solve(a); printf("%d\n", ans[a]); } } return 0; }1014 这道题我的理解完全不一样,对于5点下班这件事,我真的无语,这种坑就需要猜了
#include<bits/stdc++.h> using namespace std; const int N = 1e4+5; const int INF = 0x3f3f3f3f; typedef long long ll; int usetime[1005]; int ans[1005]; queue<pair<int,int> > Q[25]; void solve(int id, int x) { int t1 = (x-usetime[id])/60; int t2 = (x-usetime[id])%60; if(t1+8 >= 17 ) { printf("Sorry\n"); return; } t1 = x/60; t2 = x%60; printf("d:d\n", t1+8, t2); } int main() { int n, m, k, q; while(~scanf("%d %d %d %d", &n, &m, &k, &q)) { memset(ans, 0, sizeof(ans)); for(int i = 1; i <= n; ++i) { if(!Q[i].empty()) Q[i].pop(); } for(int i = 1; i <= k; ++i) { scanf("%d", &usetime[i]); } for(int i = 1; i <= min(k, n*m); ++i) { int tt = (i-1)%n + 1; Q[tt].push(make_pair(usetime[i],i)); } int ntime = 0; for(int i = min(k,n*m)+1; i <= k; ++i) { int mi = INF; int po; for(int j = 1; j <= n; ++j) { int ti = Q[j].front().first; if(mi > ti) { mi = ti; po = j; } } int t2 = Q[po].front().second; Q[po].pop(); ans[t2] = ntime+mi; ntime += mi; Q[po].push(make_pair(usetime[i],i)); for(int j = 1; j <= n; ++j) { if(j != po) { Q[j].front().first -= mi; } } } for(int j = 1; j <= n; ++j) { int wtime = ntime; while(!Q[j].empty()) { int t1 = Q[j].front().first; int t2 = Q[j].front().second; Q[j].pop(); ans[t2] = wtime+t1; wtime += t1; } } for(int i = 1; i <= q; ++i) { int a; scanf("%d", &a); if(ans[a] == 0) while(1); solve(a, ans[a]); } } return 0; } /* 2 2 7 5 1 2 6 4 3 534 2 3 4 5 6 7 */1015深坑, 1000翻转0001不合法的
#include <bits/stdc++.h> using namespace std; const int N = 1e5+5; int prime(int x) { // printf("%d\n", x); for(int i = 2; i < x; ++i) { if(x % i == 0) { return 0; } } return 1; } int main() { int n, d; while(~scanf("%d", &n)) { if(n < 0) break; scanf("%d",&d); int tt = n; vector<int> vc; while(tt) { vc.push_back(tt%d); tt /= d; } int _n = 0; if(vc[0] == 0) { printf("No\n"); continue; } for(int i = 0; i < vc.size(); ++i) { // printf("%d\n",vc[i]); _n = _n*d + vc[i]; } if(prime(n) && prime(_n)) printf("Yes\n"); else printf("No\n"); } return 0; }1016 很烦一题,我的世界一开始计算错了
#include<cmath> #include<map> #include<iostream> #include<cstring> #include<cstdio> #include<set> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int N = 1e5+5; #define MP(x, y) make_pair(x, y) int toll[30]; char s[1005][50]; struct Node{ int mon, day, hour, mina; int on; Node(int a=0, int b=0, int c=0, int d=0, int e=0):mon(a), day(b), hour(c), mina(d), on(e){} }; map<string, int> mp; int tot; map<string, int> ::iterator it; vector<Node> tim[1005]; vector< pair< pair<Node,Node>, pair<int, int> > > ans[1005][15]; int cmp(Node a, Node b) { if(a.mon != b.mon) return a.mon < b.mon; else if(a.day != b.day) return a.day < b.day; else if(a.hour != b.hour) return a.hour < b.hour; else return a.mina < b.mina; } int main() { int allhour = 0; for(int i = 0; i <= 23; ++i) { scanf("%d", &toll[i]); allhour += toll[i]; } tot = 0; int n; scanf("%d", &n); for(int i = 1; i <= n; ++i) { char tmp[10]; scanf("%s", s[i]); int a,b,c,d, e=1; scanf("%d:%d:%d:%d", &a, &b, &c, &d); scanf("%s", tmp); if(tmp[1] == 'f') e *= -1; if(mp.find(s[i]) == mp.end()) mp[s[i]] = ++tot; tim[mp[s[i]]].push_back(Node(a,b,c,d,e)); } for(int i = 1; i <= tot; ++i) { sort(tim[i].begin(), tim[i].end(), cmp); for(int j = 0; j < tim[i].size(); j += 2) { if(tim[i][j].on > 0 && j+1 < tim[i].size() && tim[i][j+1].on < 0) { int a1, a2; int t1 = toll[tim[i][j].hour]* tim[i][j].mina; for(int k = 0; k < tim[i][j].hour; ++k) t1 += toll[k]*60; int t2 = toll[tim[i][j+1].hour]* tim[i][j+1].mina; for(int k = 0; k < tim[i][j+1].hour; ++k) t2 += toll[k]*60; if(tim[i][j].day == tim[i][j+1].day) { a1 = t2-t1; }else { a1 = (allhour*60 - t1) + t2; a1 += (tim[i][j+1].day-tim[i][j].day-1) * allhour*60; } t1 = tim[i][j].mina; for(int k = 0; k < tim[i][j].hour; ++k) t1 += 60; t2 = tim[i][j+1].mina; for(int k = 0; k < tim[i][j+1].hour; ++k) t2 += 60; if(tim[i][j].day == tim[i][j+1].day) { a2 = t2-t1; }else { a2 = (24*60 - t1) + t2; a2 += (tim[i][j+1].day-tim[i][j].day-1) * 24*60; } ans[i][tim[i][j].mon].push_back( MP( MP(tim[i][j], tim[i][j+1]), MP(a2,a1) ) ); }else j--; } } for(it = mp.begin(); it != mp.end(); ++it) { int id = it->second; for(int j = 1; j <= 12; ++j) { if(ans[id][j].size() > 0) { int all = 0; for(int k = 0; k < it->first.length(); ++k) printf("%c", it->first[k]); printf(" d\n", j); for(int k = 0; k < ans[id][j].size(); ++k) { Node t1 = ans[id][j][k].first.first; Node t2 = ans[id][j][k].first.second; int t3 = ans[id][j][k].second.first; int t4 = ans[id][j][k].second.second; all += t4; printf("d:d:d d:d:d %d $%.2f\n", t1.day,t1.hour,t1.mina, t2.day,t2.hour,t2.mina ,t3, t4/100.0); } printf("Total amount: $%.2f\n", all/100.0); } } } }1017数据无话可说,我对于时间的界限还是不好掌握
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define MP(x, y) make_pair(x, y) #define FI first #define SE second const int N = 1e4+5; const int INF = 0x3f3f3f3f; struct Node{ int tim, spend, id; Node(int a=0, int b=0, int c=0):tim(a), spend(b), id(c){} }E[N]; int comtime[N]; int ans[N]; int cmp(Node a, Node b) { return a.tim < b.tim; } int windows[105]; int main() { int n, k; while(~scanf("%d %d", &n, &k)) { for(int i = 1; i <= n; ++i) { int a, b, c, d; scanf("d:d:d %d", &a,&b,&c,&d); int tt = a*60*60 + b*60 + c; if(d > 60) d = 60; E[i] = Node(tt, d, i); comtime[i] = tt; } sort(E+1, E+n+1, cmp); for(int i = 1; i <= k; ++i) windows[i] = 8*3600; int ntime = 0; for(int i = 1; i <= n; ++i) { // printf("%d ", E[i].tim); int mx = INF, po; for(int j = 1; j <= k; ++j) { if(mx > windows[j]) { mx = windows[j]; po = j; } } mx = max(E[i].tim, mx); ans[E[i].id] = mx; // printf("%d\n", mx); windows[po] = mx + E[i].spend*60; } int all = 0; int cnt = 0; for(int i = 1; i <= n; ++i) { // printf("%d %d\n", ans[i], comtime[i]); if(comtime[i] > 17*3600) { continue; } cnt ++; int tt = ans[i]-comtime[i]; all += tt; } if(cnt) printf("%.1f\n", all/60.0/cnt); else printf("0.0\n"); } return 0; }1018把我写成狗,我真的得掌握dijsktra+dfs这种方法,比我这个好多了 当然别忘了send,back可能同时存在,这很重要
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define MP(x, y) make_pair(x, y) #define FI first #define SE second const int N = 505; const int INF = 0x3f3f3f3f; int Cmax; int n, sp, m; int C[N]; struct Node{ int to, nx, dis; }E[N*N*2]; int head[N], tot; void add(int a, int b, int c) { E[tot].to = b; E[tot].nx = head[a]; E[tot].dis = c; head[a] = tot++; } struct HeapNode{ int po, di; HeapNode(int a=0, int b=0):po(a), di(b){} bool operator <(const HeapNode & T) const{ return di > T.di; } }; int dis[N]; int vis[N]; struct Pode{ int send, bak, pre, preid; Pode(int a=0, int b=0, int c=0, int d=0):send(a), bak(b), pre(c), preid(d){} }; vector<Pode> bike[N]; void dijstra(int st) { memset(dis, INF, sizeof(dis)); memset(vis, 0, sizeof(vis)); for(int i = 0; i <= n; ++i) bike[i].clear(); dis[st] = 0; bike[st].push_back(Pode(0,0,0,0)); priority_queue<HeapNode> Q; Q.push(HeapNode(st, dis[st])); while(!Q.empty()) { int x = Q.top().po; Q.pop(); if(vis[x]) continue; vis[x] = 1; for(int i = head[x]; ~i; i = E[i].nx) { int to = E[i].to; if(dis[to] > dis[x]+E[i].dis) { dis[to] = dis[x]+E[i].dis; bike[to].clear(); for(int j = 0; j < bike[x].size(); ++j) { int t1 = bike[x][j].send; int t2 = bike[x][j].bak; if(Cmax <= C[to]) t2 += C[to]-Cmax; else { int t3 = Cmax-C[to]; int t4 = min(t2, t3); t2 -= t4; t3 -= t4; if(t3) t1 += t3; } bike[to].push_back(Pode(t1, t2, x, j)); } Q.push(HeapNode(to, dis[to])); } else if(dis[to] == dis[x]+E[i].dis) { map<pair<int,int> , int> mmp; mmp.clear(); for(int j = 0; j < bike[to].size(); ++j) { mmp[ MP(bike[to][j].send, bike[to][j].bak) ] ++; } for(int j = 0; j < bike[x].size(); ++j) { int t1 = bike[x][j].send; int t2 = bike[x][j].bak; if(Cmax <= C[to]) t2 += C[to]-Cmax; else { int t3 = Cmax-C[to]; int t4 = min(t2, t3); t2 -= t4; t3 -= t4; if(t3) t1 += t3; } if(mmp.find(MP(t1, t2)) == mmp.end()) bike[to].push_back(Pode(t1, t2, x, j)); } } } } } void dfs(int x, int id) { // printf("%d %d\n", x, id); if(x == 0) { printf("0"); return; } int pre = bike[x][id].pre; int preid = bike[x][id].preid; dfs(pre, preid); printf("->%d", x); } void solve() { int a1 = INF, a2 = INF; int id; for(int i = 0; i < bike[sp].size(); ++i) { if(a1 > bike[sp][i].send) { a1 = bike[sp][i].send; a2 = bike[sp][i].bak; id = i; }else if(a2 >bike[sp][i].bak && a1 == bike[sp][i].send) { a2 = bike[sp][i].bak; id = i; } } printf("%d ", bike[sp][id].send); dfs(sp, id); printf(" %d\n", bike[sp][id].bak); // if(bike[sp][id].send && bike[sp][id].bak) while(1); } int main() { C[0] = 0; while(~scanf("%d %d %d %d", &Cmax, &n, &sp, &m)) { Cmax /= 2; memset(head, -1, sizeof(head)); tot = 0; for(int i = 1; i <= n; ++i) { scanf("%d", &C[i]); } for(int i = 0; i < m; ++i) { int a, b, c; scanf("%d %d %d",&a,&b,&c); add(a, b, c); add(b, a, c); } dijstra(0); solve(); } return 0; }1019
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<cmath> using namespace std; const int INF = 0x3f3f3f3f; const int N = 1e6+5; const int M = 3e5+5; int main() { int n, b; while(~scanf("%d %d",&n,&b)) { int tmp = n; vector<int> ans; while(tmp) { ans.push_back(tmp%b); tmp /= b; } int fl = 1; int len = ans.size(); for(int i = 0; i < len/2; ++i) { if(ans[i] != ans[len-i-1]) { fl = 0; break; } } if(fl) printf("Yes\n"); else printf("No\n"); if(n == 0) { printf("0\n"); continue; } for(int i = len-1; i >= 0; --i) { if(i != len-1) printf(" "); printf("%d", ans[i]); } printf("\n"); } return 0; }1020
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<cmath> #include<queue> using namespace std; const int INF = 0x3f3f3f3f; const int N = 1e6+5; const int M = 3e5+5; int a[35]; int b[35]; struct Node{ int l,r,L,R; Node(int a=0, int b=0, int c=0, int d=0):l(a), r(b), L(c), R(d){} }; int main() { int n; while(~scanf("%d", &n)) { // memset(head, -1, sizeof(head)); tot = 0; for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); for(int i = 1; i <= n; ++i) scanf("%d", &b[i]); queue<Node> Q; Q.push(Node(1, n, 1, n)); int fl = 1; int cnt = 0; while(!Q.empty()) { Node t = Q.front(); Q.pop(); if(t.l > t.r) continue; /* printf("%d\n", cnt); if(cnt < 10) { printf("%d\n", t.r); cnt ++; }*/ int tag = a[t.r]; if(fl) { fl = 0; }else printf(" "); printf("%d", tag); if(t.l == t.r) continue; int M; for(int i = t.L; i <= t.R; ++i) { if(b[i] == tag) { M = i-1; break; } } int m = t.l+(M-t.L); Q.push(Node(t.l, m, t.L, M)); Q.push(Node(m+1, t.r-1, M+2, t.R)); } printf("\n"); } return 0; }转载于:https://www.cnblogs.com/Basasuya/p/8433712.html