D. Generalized Roman Numerals [思维dp]
dp
#pragma GCC optimize(2) #pragma GCC optimize(3) unordered_set<int> save[maxn][maxn]; int mp[1000]; int num[10000007]; void QuickSort(int l,int r) { if(l>=r) return; int left=l,right=r;// ll temp=num[(left+right)/2];//设左边的为基值 int mid=(left+right)/2; while(left<right) { //相等的 return;就可以了 while(num[left]<temp) left++; while(num[right]>temp) right--; if(left<=right) { ll stemp=num[left]; num[left]=num[right]; num[right]=stemp; left++; right--; } } QuickSort(l,right); QuickSort(left,r); } int main() { mp['I'] = 1; mp['V'] = 5; mp['X'] = 10; mp['L'] = 50; mp['C'] = 100; char s[55]; int kase = 0; while(scanf("%s",s) != EOF) { if(s[0] == '0') break; int len = strlen(s); for(int i=0; i<=len; i++) { for(int j=0; j<=len; j++) { save[i][j].clear(); } } for(int i=0; i<len; i++) { save[i][i].insert(mp[s[i]]);//自己到自己只能是当前字符 } // meiju 长度 for(register int i=2; i<=len; i++) { for(register int j=0; j+i<=len; j++) { int st = j; int ed = j+i-1; //ed - st + 1 => length=i for(register int md=j; md<ed; ++md) { for(auto A : save[st][md]) { for(auto B : save[md+1][ed]) { if(A >= B) save[st][ed].insert(A + B); else save[st][ed].insert(- A + B); } } } } } vector<int> v; int idx = 0; for(int x:save[0][len-1]) v.push_back(x); // for(int x:save[0][len-1]) { // num[++idx] = x; // } sort(v.begin(), v.end()); // sort(num+1,num+1+idx); // QuickSort(1, idx); // v.erase(unique(v.begin(), v.end()),v.end()); printf("Case %d: ",++kase); // for(int x: v) printf("%d ", x); for(int i=0; i<v.size(); i++) { printf("%d%c",v[i],i == v.size()-1?'\n':' '); } // puts(""); // for(int i=1; i<=idx; i++) { // printf("%d%c",num[i],i == idx?'\n':' '); // } } return 0; }
E. Inspectors [拆点跑最小费用最大流]
/*** keep hungry and calm PushyTao!***/ typedef pair<ll, ll> PLL; struct Edge { int u, v, cap, flow, cost; Edge(int _u, int _v, int _cap, int _flow, int _cost) { u = _u, v = _v, cap = _cap, flow = _flow, cost = _cost; } }; struct MinCostMaxFlow { int n, m; vector<Edge> edges; vector<int> G[maxn]; int vis[maxn], dis[maxn], p[maxn], a[maxn]; void init(int x) { this->n = x; for (int i = 0; i <= x; i++) G[i].clear(); edges.clear(); } void add(int u, int v, int cap, int cost) { edges.push_back(Edge(u, v, cap, 0, cost)); edges.push_back(Edge(v, u, 0, 0, -cost)); m = edges.size(); G[u].push_back(m - 2); G[v].push_back(m - 1); } bool BellmanFord(int s, int t, ll &flow, ll &cost) { for (int i = 0; i <= n; i++) dis[i] = 0x3f3f3f3f; memset(vis, 0, sizeof vis); queue<int> que; que.push(s); dis[s] = 0, vis[s] = 0, p[s] = 0, a[s] = 0x3f3f3f3f; while (que.size()) { int u = que.front(); que.pop(); vis[u] = 0; /// not in the queue for (int i = 0; i < G[u].size(); i++) { int id = G[u][i]; Edge e = edges[id]; int to = e.v; if (e.cap > e.flow && dis[to] > dis[u] + e.cost) { dis[to] = dis[u] + e.cost; p[to] = id; a[to] = min(a[u], e.cap - e.flow); if (!vis[to]) { que.push(to); vis[to] = 1; } } } } if (dis[t] >= 0x3f3f3f3f) return false; flow += a[t]; cost += 1LL * dis[t] * 1LL * a[t]; for (int u = t; u != s; u = edges[p[u]].u) { edges[p[u]].flow += a[t]; edges[p[u] ^ 1].flow -= a[t]; } return true; } PLL MinCostAndMaxFlow(int s, int t) { ll flow = 0; ll cost = 0; while (BellmanFord(s, t, flow, cost)); return {flow, cost}; } } solve; int n, m, s, t; int main() { /** cin >> n >> m >> s >> t; solve.init(n); for (int i = 1; i <= m; i++) { int u = read, v = read, flow = read, cost = read; solve.add(u, v, flow, cost); } PLL ans = solve.MinCostAndMaxFlow(s, t); cout << ans.first << ' ' << ans.second << endl; **/ int _ = read; for(int kase=1; kase<=_; kase++) { n = read; solve.init(1003); for(int i=1; i<=n; i++) { solve.add(0,i,1,0);// s <-> i_in solve.add(i+n,1001,1,0);// i_out <-> t for(int j=i+1; j<=n; j++) { int value = read; solve.add(i,j+n,1,value);// in_i <-> j_out solve.add(j,i+n,1,value);// in_j <-> i_out } } PLL p = solve.MinCostAndMaxFlow(0,1001); // cout << p.first << endl; printf("Case %d: %d\n",kase, p.second); } return 0; } /** 2 4 10 20 10 10 20 10 4 15 20 10 10 20 15 -> Case 1: 40 Case 2: 40 **/
H. Time Warp [模拟]
可以参考
/*** keep hungry and calm PushyTao!***/ void print(int kase, ll seco) { int h,m,s; h = m = s = 0; seco = (seco + 12 * 60 * 60) % (12 * 60 * 60);//;// h = seco / 3600 + 1; m = seco % 3600 / 60; s = seco % 60; printf("Case %d: %d:%02d:%02d\n",kase, h,m,s); } void solve(int a,int b,string c,int kase) { if(c[0] == 'a') { int cur = 30 * (12 - b); int need = 0; if(a > cur) need = a - cur; else need = 360 - cur + a; int t = round(need / (11.0 / 120.0)); print(kase, 3600 * (b - 1) + t); } else if(c[0] == 't') { int cur = 30 * (12 - b); int need = 0; if(a < cur) need = -(a - cur); else need = 360 + cur - a; int t = round(need / (11.0 / 120.0)); print(kase, 3600 * (b - 1) - t); } } int main() { int _ = read; int kase; for(kase = 1; kase <= _; kase++) { string c; int a = read; cin >> c; int b = read; solve(a,b,c,kase); } return 0; } /** **/
A. Cure for the Common Code [KMP]
#include <bits/stdc++.h> typedef long long ll; template<typename T> std::istream& operator>> (std::istream& in, std::vector<T>& vt) { for (auto& i : vt) in >> i; return in; } template<typename T> std::ostream& operator<< (std::ostream& out, const std::vector<T>& vt) { for (auto& i : vt) out << i << " "; out << std::endl; return out; } void printAll() { } template<typename T1, typename... T2> void printAll(const T1& first, const T2&... second) { std::cout << first; if (sizeof...(second)) { std::cout << ", "; } printAll(second...); } template<typename T1, typename... T2> void print(const T1& first, const T2&... second) { std::cout << "["; printAll(first, second...); std::cout << "]" << std::endl; } #define N (int)(5e2 + 10) struct Kmp { static int nxt[N]; // nxt[i] // 表示前i个字母，下标应该转移到nex[i] // 本质含义是最长前后缀，但是由于字符串从0开始计数的，所以正好指向的是最长前后缀的前缀的下一个位置，即需要匹配的位置 private: static void init() { memset(nxt, 0, sizeof(nxt)); } public: static int get(const std::string& s1, bool init = false) { const int& n = s1.size(); for (int i = 1, j = 0; i < n; i++) { while (j && s1[i] != s1[j]) j = nxt[j - 1]; if (s1[i] == s1[j]) j++; nxt[i] = j; } int len = n - nxt[n - 1]; return len; } }; #define print(...) int Kmp::nxt[]{}; int getBitCnt(int n) { int res = 0; while (n) { res += 1; n /= 10; } return res; } int main() { print(getBitCnt(9)); int T = 1; std::string str; while (std::cin >> str) { if (str == "0") break; const int& n = str.size(); std::vector<std::vector<int>> f(n, std::vector<int>(n, 1e9)); for (int i = 0; i < n; i++) { f[i][i] = 1; } for (int len = 2; len <= n; len++) { for (int l = 0, r = len - 1; r < n; l++, r++) { for (int k = l; k < r; k++) { f[l][r] = std::min(f[l][r], f[l][k] + f[k + 1][r]); } int cnt = r - l + 1; int len = Kmp::get(str.substr(l, cnt), true); if (l == 1 && r == 3) { print(len); } if (cnt % len == 0) { int tmp = 0; if (len >= 2) tmp += 2; tmp += f[l][l + len - 1]; tmp += getBitCnt(cnt / len); f[l][r] = std::min(f[l][r], tmp); } } } print(str.substr(0, 10)); printf("Case %d: %d\n", T++, f[0][n - 1]); } return 0; }
