A - The Third Cup is Free
題意：每買三杯飲料，最便宜的一杯免費(fèi)。簽到題
AC代碼：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdlib>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
bool cmp(int a, int b) {
return a > b;
}
int main() {
int T, n;
int kase = 0;
int ans = 0;
scanf("%d", &T);
while(T--) {
scanf("%d",&n);
ans = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
ans += a[i];
}
sort(a+1, a+n+1, cmp);
for(int i = 1; i <= n; i++) {
if(i%3 == 0)
ans -= a[i];
}
printf("Case #%d: %d\n", ++kase, ans);
}
return 0;
}
B - Wash
題意：有L件衣服，n臺(tái)洗衣機(jī)，m臺(tái)烘干機(jī)，每臺(tái)洗衣機(jī)的工作時(shí)間為W1,W2,...,Wn，烘干機(jī)的工作時(shí)間為D1,D2,...,Dn，問洗完這些衣服需要的最短時(shí)間。
?1≤T≤100
?1≤L≤1e6
?1≤N,M≤1e5
?1≤Wi,Di≤1e9
思路：貪心，但賽場(chǎng)上愣是沒想出來。洗衣機(jī)的工作時(shí)間比較好貪，用一個(gè)優(yōu)先隊(duì)列，每次取工作時(shí)間最短的洗衣機(jī)，然后將洗衣機(jī)的結(jié)束時(shí)間 += 工作時(shí)間再壓回隊(duì)列即可。主要是對(duì)烘干機(jī)的處理，這里應(yīng)該是讓結(jié)束洗衣時(shí)間越晚的衣服盡量用快的烘干機(jī)，這樣時(shí)間一長(zhǎng)+一短，才能夠使得總時(shí)間盡量的短。所以我們?cè)谶@里倒序處理每件衣服的烘干。
AC代碼：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+10;
struct node {
ll time, endtime;
friend bool operator < (node a, node b) {
return a.endtime > b.endtime;
}
};
ll ans[maxn];
int main() {
int T, l, n, m;
ll t;
int kase = 0;
scanf("%d", &T);
while(T--) {
priority_queue<node> que1, que2;
scanf("%d%d%d", &l, &n, &m);
for(int i = 0; i < n; i++) {
scanf("%lld", &t);
que1.push((node){t,t});
}
for(int j = 0; j < m; j++) {
scanf("%lld", &t);
que2.push((node){t,t});
}
node temp;
for(int i = 1; i <= l; i++) {
temp = que1.top();
que1.pop();
ans[i] = temp.endtime;
temp.endtime += temp.time;
que1.push(temp);
}
ll endans = 0;
for(int i = l; i >= 1; i--) {
temp = que2.top();
que2.pop();
endans = max(endans, temp.endtime + ans[i]);
temp.endtime += temp.time;
que2.push(temp);
}
printf("Case #%d: %lld\n", ++kase, endans);
}
return 0;
}
C - Mr.Panda and Survey
D - Game Leader
題意：給出社交網(wǎng)絡(luò)中Tom的朋友排行榜（Tom）也在排行榜中。排行榜是按照每個(gè)人的評(píng)分排序的。給出的排行中的數(shù)字是該人在C[i]個(gè)榜單上占據(jù)第一。同時(shí)給出m組朋友關(guān)系，表示這兩個(gè)人是朋友，當(dāng)然也有一些朋友關(guān)系是Tom不知道的。問有最少有多少個(gè)陌生人的榜一是Tom的朋友。
思路：優(yōu)先隊(duì)列貪心。貪了很久沒貪明白……待補(bǔ)。
E - Problem Buyer
題意：給出n個(gè)區(qū)間，m個(gè)數(shù)，讓你任意選k個(gè)數(shù)，使一定能包含這m個(gè)數(shù)，一個(gè)區(qū)間只能包含一個(gè)數(shù) 求最小的k
思路：據(jù)說是個(gè)肥腸難想的貪心……待補(bǔ)。
F - Periodical Cicadas
G - Pandaland
題意：給你一個(gè)m 個(gè)邊的無向圖，要求在圖上找一個(gè)邊權(quán)之和最小的環(huán)
思路：dijkstra暴力+剪枝。由于最小環(huán)肯定會(huì)包含某一條邊，那么我們可以通過枚舉每條邊，以邊的兩個(gè)端點(diǎn)為s和t，令這條邊的權(quán)為INF，跑dijkstra，那么跑出來的 d[t] 加上這條邊初始的邊權(quán)即為包含該邊的最小環(huán)權(quán)值。每次跑完取最小值即可。
預(yù)處理把坐標(biāo)離散化。注意判最后若ans =INF，直接改為ans = 0。
剪枝：如果優(yōu)先隊(duì)列中最小邊權(quán) + 被枚舉的邊的初始邊權(quán) >= ans，可以直接break掉。
AC代碼：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <set>
using namespace std;
const int maxn = 4000 + 5;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pr;
int d[2*maxn];
map<pr, int> mp;
int ans;
int cnt;
int s, t;
struct edge { int to, cost; };
struct edge2 { int ID1, ID2, cost; }e[maxn];
vector<edge> g[maxn];
int getid(pr p) {
if(!mp[p]) mp[p] = ++cnt;
return mp[p];
}
void dijkstra(int s, int cst) {
priority_queue<pr, vector<pr>, greater<pr> > que;
for(int i = 1; i <= cnt; i++)
d[i] = INF;
d[s] = 0;
que.push(make_pair(0,s));
while(!que.empty()) {
pr now = que.top();
que.pop();
int u = now.second;
if(now.first + cst >= ans) break;
if(d[u] < now.first)
continue;
for(int i = 0; i < (int)g[u].size(); ++i) {
edge edg = g[u][i];
int v = g[u][i].to;
if( u == s && v == t )
edg.cost = INF;
if( d[u] + edg.cost < d[v]) {
d[v] = d[u] + edg.cost;
que.push(make_pair(d[v], v));
}
}
}
}
void init() {
for(int i = 1; i <= cnt; i++)
g[i].clear();
mp.clear();
cnt = 0;
}
int main() {
int T, m;
int kase = 0;
scanf("%d", &T);
int x1, y1, x2, y2, cost, id1, id2;
while(T--) {
init();
scanf("%d", &m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &cost);
id1 = getid(make_pair(x1, y1));
id2 = getid(make_pair(x2, y2));
e[i] = (edge2){id1, id2, cost};
g[id1].push_back((edge){id2, cost});
g[id2].push_back((edge){id1, cost});
}
/*
map<pr, int>::iterator it = mp.begin();
for( ; it != mp.end(); ++it)
cout << it->first.first << " " << it->first.second << " " << it->second << endl;
*/
ans = INF;
for(int i = 0; i < m; i++) {
s = e[i].ID1, t = e[i].ID2;
dijkstra(s, e[i].cost);
//cout << d[t] << endl;
ans = min(ans, d[t] + e[i].cost);
}
if(ans >= INF) ans = 0;
printf("Case #%d: %d\n", ++kase, ans);
}
return 0;
}
H - Engineer Assignment
題意：有n項(xiàng)工作，m個(gè)雇員。每一項(xiàng)工作涉及到C[i] ( 1 ≤ C[i] ≤ 3 )個(gè)領(lǐng)域，每個(gè)人擅長(zhǎng)D[i] ( 1 ≤ D[i] ≤ 3 )個(gè)領(lǐng)域，領(lǐng)域由1～100的編號(hào)表示。
思路：比賽的時(shí)候感覺是匹配，但是建不出圖來，比較奇妙的是C[i]和D[i]都驚人的小。賽后查了一下居然是狀壓dp……
I - Mr. Panda and Crystal
題意：島上有n種寶石，有的寶石可以用魔力值合成，有的寶石不可以用魔力值合成。還有k種配方，即由幾種寶石合成另一種。每一種寶石都有一個(gè)售價(jià)?，F(xiàn)在，Panda有m的魔力值，問Panda得到的寶石最多能賣出多少錢。
思路：可以通過配方用消耗魔力值低的寶石去合成消耗魔力值低或者不能夠用魔力值合成但是售價(jià)高的寶石，只要能夠知道每個(gè)寶石最少需要多少魔力值合成，就可以將模型轉(zhuǎn)化為物品重量為最低魔力值，價(jià)值為寶石售價(jià)，容量為m的完全背包。比賽的時(shí)候開這個(gè)題開的太晚了，只剩不到一個(gè)小時(shí)，所以沒想清楚關(guān)于計(jì)算每個(gè)寶石合成所需要的“最低魔力值”如何計(jì)算，曾經(jīng)想過跑最短路，但是當(dāng)時(shí)沒想清楚怎么建圖。dijkstra處理出來之后，就是非常水的完全背包了。
注意每個(gè)寶石消耗的魔力值c[i]不能夠初始化為INF，因?yàn)橛械膶毷赡茏罱K也無法由任何方式合成，因此RE了好幾次。其實(shí)直接把一開始無法用魔力之合成的寶石c[i]定義為m+1就可以了。
AC代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int maxn = 210;
const int INF = 0x3f3f3f3f;
int c[maxn], w[maxn];
int dp[10010];
vector<int> g[maxn];
bool vis[maxn];
int m, n, k;
struct node {
int to, cost;
bool operator < (const node n_) const {
return cost > n_.cost;
}
};
priority_queue<node> que;
struct node2 {
int goal;
vector<pair<int, int> > vec;
}e[maxn];
void check() {
puts("------------\n");
for(int i = 1; i <= n; i++)
printf("%d %d\n", i, c[i]);
puts("\n------------");
}
int getsum(node2& nd) {
int sum = 0;
for(int i = 0; i < nd.vec.size(); i++) {
sum += nd.vec[i].second * c[nd.vec[i].first];
}
return sum;
}
void dijkstra() {
int u, newcost;
while(!que.empty()) {
node nd = que.top();
que.pop();
u = nd.to;
if(vis[u]) continue;
vis[u] = true;
for(int i = 0; i < (int)g[u].size(); i++) {
node2& nd2 = e[g[u][i]];
newcost = getsum(nd2);
if(newcost < c[nd2.goal]) {
c[nd2.goal] = newcost;
que.push((node){nd2.goal, c[nd2.goal]});
}
}
}
}
void init() {
memset(vis, 0, sizeof vis);
memset(dp, 0, sizeof dp);
}
int main()
{
int T;
int kase = 0;
scanf("%d", &T);
while(T--) {
init();
scanf("%d%d%d", &m, &n, &k);
int flag;
for(int i = 1; i <= n; i++) {
g[i].clear();
scanf("%d", &flag);
if(flag) {
scanf("%d", &c[i]);
que.push((node){i, c[i]});
}
else {
c[i] = m+1;
}
scanf("%d", &w[i]);
}
int sum_, type_, num_;
for(int i = 0; i < k; i++) {
scanf("%d%d", &e[i].goal, &sum_);
e[i].vec.clear();
for(int j = 0; j < sum_; j++) {
scanf("%d%d", &type_, &num_);
e[i].vec.push_back(make_pair(type_, num_));
g[type_].push_back(i);
}
}
dijkstra();
//check();
for(int i = 1; i <= n; i++) {
for(int v = c[i]; v <= m; v++) {
dp[v] = max(dp[v], dp[v-c[i]]+w[i]);
}
}
printf("Case #%d: %d\n", ++kase, dp[m]);
}
return 0;
}
J - Worried School
思路：據(jù)說是個(gè)模擬，隊(duì)友A的
AC代碼：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <queue>
#include <string>
#include <set>
using namespace std;
int n;
string str, s;
queue<string> q[6];
set<string> st;
int cal() {
st.clear();
int m = 0;
for(int i = 0; i < 100; ++i) {
if(q[i % 5].front() == str)
return n - m;
if(st.find(q[i % 5].front()) == st.end()) {
++m;
st.insert(q[i % 5].front());
if(m == n)
return 0;
}
q[i % 5].pop();
}
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T, t = 0;
cin >> T;
while(T--) {
for(int i = 0; i < 6; ++i) {
while(!q[i].empty())
q[i].pop();
}
cin >> n >> str;
for(int i = 0; i < 6; ++i) {
for(int j = 0; j < 20; ++j) {
cin >> s;
q[i].push(s);
}
}
int ans = cal(), i = 0;
while(!q[5].empty() && i < ans) {
if(q[5].front() == str) {
ans = -1;
break;
}
if(st.find(q[5].front()) == st.end()) {
st.insert(q[5].front());
++i;
}
q[5].pop();
}
cout << "Case #" << ++t << ": ";
if(ans == -1)
cout << "ADVANCED!" << endl;
else
cout << ans << endl;
}
return 0;
}
K - Lazors
L - Daylight Saving Time
題意：有關(guān)夏令時(shí)。每年3月份的第2個(gè)星期天的2:00會(huì)躍變?yōu)?:00，同時(shí)標(biāo)準(zhǔn)時(shí)從PST變?yōu)镻DT；每年11月份的第1個(gè)星期天的2:00會(huì)躍變?yōu)?:00，同時(shí)標(biāo)準(zhǔn)時(shí)從PDT變?yōu)镻ST；現(xiàn)在給出一個(gè)介于“2007-01-01 00:00:00” 和 “2100-12-31 23:59:59”的時(shí)間點(diǎn)，判斷這個(gè)時(shí)間點(diǎn)是PDT/PST/Both/Neither。
思路：對(duì)于在三月份和十一月份的日子，用基姆拉爾森公式算一下這一天是星期幾，如果在變動(dòng)夏令時(shí)的這一天的話具體判斷一下時(shí)間，其他的直接找PST/PDT。比較坑的是3月第2個(gè)星期天的[2:00,3:00)屬于Neither，11月份第1個(gè)星期天的[1:00,2:00)是Both，至于這個(gè)半閉半開區(qū)間，沒讀出來，有點(diǎn)迷，交了兩發(fā)wa猜的那個(gè)邊界。感覺四級(jí)要gg。
AC代碼：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdlib>
using namespace std;
int weekday(int y, int m, int d) {
if(m == 1 || m == 2) {
m += 12;
y--;
}
int w = (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7;
return w;//0->monday
}
int main() {
int T;
scanf("%d", &T);
int kase = 0;
int flag = 0;
//1:pst, 2:pdt, 3:both, 4:neither;
int year, month, date, hour, minute, second;
while(T--) {
scanf("%d-%d-%d %d:%d:%d",&year, &month, &date, &hour, &minute, &second);
if(month == 3) {
int i;
int cnt = 0;
for(i = 1; i <= 31; i++) {
if(weekday(year, month, i) == 6) {
cnt++;
if(cnt == 2)
break;
}
}
if(date==i) {
if(hour<2) flag = 1; //pst
else if(hour >= 3) flag = 2; //pdt
else flag = 4; //neither
}
else if(date < i) flag = 1; //pst
else flag = 2; //pdt;
}
else if(month == 11) {
int i;
for(i = 1; i <= 30; i++) {
if(weekday(year, month, i) == 6)
break;
}
if(date==i) {
if(hour<1) flag = 2; //pdt
else if(hour >= 2) flag = 1; //pst
else flag = 3; //both
}
else if(date < i) flag = 2; //pdt
else flag = 1; //pst
}
else if(month > 3 && month < 11) flag = 2; //pdt
else flag = 1; //pst
printf("Case #%d: ", ++kase);
if(flag == 1) printf("PST\n");
else if(flag == 2) printf("PDT\n");
else if(flag == 3) printf("Both\n");
else if(flag == 4) printf("Neither\n");
}
return 0;
}
