A . The Alphabet Sticker
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; int main(){ int _;cin>>_; while(_--){ string s;cin>>s; ll l=0,r=s.size()-1; while(s[l]=='?') l++; while(s[r]=='?') r--; ll ans=1ll,tmp=0; for(int i=l;i<=r;i++){ if(s[i]=='?'){ tmp=i; while(s[tmp]=='?') tmp++; ll now=tmp-i+1; if(s[i-1]!=s[tmp]) ans=ans*now%mod; i=tmp; } } cout<<ans<<endl; } return 0; }
C . Increasing Shortest Path
排序升序加边跑dp
/*** keep hungry and calm PushyTao!***/ struct node { int u, v, w; friend bool operator<(node a, node b) { return a.w < b.w; } } e[3007]; int dp[157][157][157]; int mp[157][157]; int main() { int _ = read; while (_--) { int n = read, m = read, q = read; memset(mp, 0x3f3f3f3f, sizeof mp); for (int i = 1; i <= m; i++) { // int u = read, v = read, w = read; // mp[u][v] = min(mp[u][v], w); e[i].u = read, e[i].v = read, e[i].w = read; } /** int idx = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if(mp[i][j] < 0x3f3f3f3f) { idx ++; e[idx].u = i; e[idx].v = j; e[idx].w = mp[i][j]; } } } **/ sort(e + 1, e + 1 + m); memset(dp, 0x3f3f3f3f, sizeof dp); for (int i = 1; i <= n; i++) dp[i][i][0] = 0; //自己到自己的距离是0 for (int i = 1; i <= m; i++) { for (int qi = 1; qi <= n; qi++) { for (int skp = 1; skp <= n - 1; skp++) { // len max n-1 dp[qi][e[i].v][skp] = min(dp[qi][e[i].v][skp], dp[qi][e[i].u][skp - 1] + e[i].w); } } } while (q--) { int x = read, y = read, c = read; c = min(c, n - 1); itn ans = 0x3f3f3f3f; for (int i = 0; i <= c; i++) ans = min(ans, dp[x][y][i]); if (ans == 0x3f3f3f3f) puts("-1"); else printf("%d\n", ans); } } return 0; } /** 1 8 9 3 1 2 1 2 3 2 3 4 3 4 5 12 5 8 7 1 6 8 6 4 9 1 7 5 7 4 4 1 4 2 1 4 3 1 4 1 **/
D . Cup of Cowards
#include <bits/stdc++.h> typedef long long ll; #pragma region Debug 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; } #pragma endregion #define N (int)(5e2 + 10) struct Node { int h; long long d, c; friend bool operator< (Node& A, Node& B) { if (A.d * B.c != B.d * A.c) { return A.d * B.c > B.d * A.c; } return A.c < B.c; } }; long long L; long long sufDam[N]; std::vector<Node> v(5); long long cost, dam; void dfs(int dep, ll curCost, ll curDam) { if (curDam >= L) { if (curCost < cost) { cost = curCost; dam = curDam; } else if (curCost == cost) { dam = std::min(dam, curDam); } return; } if (dep == 5) return; if (curDam + sufDam[dep] < L) return; ll rouDam = L - curDam; ll cnt = (rouDam + (v[dep].d - 1)) / v[dep].d; if ((cnt - 1) * v[dep].c + curCost > cost) return; if (cnt > v[dep].h) cnt = v[dep].h; for (int j = cnt; j >= 0; j--) { dfs(dep + 1, curCost + 1LL * j * v[dep].c, curDam + 1LL * j * v[dep].d); } } int main() { int T; std::cin >> T; while (T--) { std::cin >> L; for (auto& [h, d, c] : v) { std::cin >> h >> d >> c; } sort(v.begin(), v.end()); sufDam[4] = 1LL * v[4].h * v[4].d; for (int i = 3; i >= 0; i--) { sufDam[i] = sufDam[i + 1] + 1LL * v[i].h * v[i].d; } cost = LLONG_MAX, dam = LLONG_MAX; dfs(0, 0, 0); if (cost == LLONG_MAX) { std::cout << "We are doomed!!" << std::endl; } else { std::cout << cost << " " << dam << std::endl; } } return 0; } /* 2 3 4 3 1 2 2 3 2 31 15 D题题意： 输入 T L 五组H, D, C L表示怪物的总血量 五个玩家 H表示当前玩家可以攻击的次数限制 D表示每次攻击造成的伤害 C表示花费 问杀死怪物的最小花费和最小伤害 */
E . Balloons Colors
int a[107]; int main() { int _ = read; while(_--) { int n = read; a[1] = read,a[n] = read; int f1 = 0, f2 = 0; for(int i=1;i<=n;i++) { int x = read; if(x == a[1] && i == 1) f1 = 1; if(x == a[n] && i == n) f2 = 1; } if(f1 && f2) puts("BOTH"); else if(f1) puts("EASY"); else if(f2) puts("HARD"); else puts("OKAY"); } return 0; }
F . NASSA’s Robot
int main() { int _ = read; while(_--) { string s; cin >> s; int _not = 0,x = 0,y = 0; for(int i=0; i<s.size(); i++) { if(s[i] == 'U') y ++; else if(s[i] == 'D') y --; else if(s[i] == 'L') x --; else if(s[i] == 'R') x ++; else _not ++; } printf("%d %d %d %d\n",x-_not,y-_not,x+_not,y+_not); } return 0; }
G . The Stones Game
int a[107]; int main() { int _ = read; while(_--) { int n = read, m = read, x = read; n -= x; if(n % m) puts("NO"); else puts("YES"); } return 0; }
I . Omar Loves Candies
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; int a[1100][1100],sum[1100][1100]; inline int Max(int a, int b) { return a > b ? a : b; } int main(){ int _;scanf("%d",&_); while(_--){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; int ans=-1e9; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ ans=Max(ans,sum[n][m]-sum[n][j-1]-sum[i-1][m]+sum[i-1][j-1]); //cout<<i<<" "<<j<<" "<<ans<<endl; } printf("%d\n",ans); } return 0; }
J . Modified LCS
#include <bits/stdc++.h> typedef long long ll; #pragma region Debug 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; } #pragma endregion #define N (int)(5e2 + 10) using num = ll; num exgcd(num a, num b, num& x, num& y) { if (b == 0) { x = 1, y = 0; return a; } num g = exgcd(b, a % b, y, x); y -= a / b * x; return g; } ll get(num n1, num f1, num d1, num n2, num f2, num d2) { num a = d1, b = -d2, c = f2 - f1; num x = 0, y = 0; num g = exgcd(a, b, x, y); if (c % g) return 0; x = x * (c / g); y = y * (c / g); num dx = abs(b / g); num dy = abs(a / g); while (x < 0 || y < 0) { x += dx; y += dy; } while (x >= 0 && y >= 0) { x -= dx; y -= dy; } while (x < 0 || y < 0) { x += dx; y += dy; } //print(x, rou, a / g); num cnt1 = (n1 - x - 1) / dx + 1; num cnt2 = (n2 - y - 1) / dy + 1; //print(cnt1, cnt2); return std::min(cnt1, cnt2); } int main() { int T; std::cin >> T; while (T--) { ll n1, f1, d1; ll n2, f2, d2; std::cin >> n1 >> f1 >> d1; std::cin >> n2 >> f2 >> d2; std::cout << get(n1, f1, d1, n2, f2, d2) << std::endl; } return 0; }
K . Mario Kart [01背包Dijkstra]
int head[1007]; struct node { int v,nex,w; } e[maxn]; int cnt = 0; void add(int u,int v,int w) { e[cnt].v = v; e[cnt].w = w; e[cnt].nex = head[u]; head[u] = cnt ++; } int a[1007]; int dp[maxn]; int c[maxn],v[maxn],dis[maxn],vis[maxn]; void init() { cnt = 0; memset(head,-1,sizeof head); memset(dp,0x3f3f,sizeof dp); memset(dis,0x3f3f3f3f,sizeof dis); memset(vis,0,sizeof vis); } typedef pair<int,int> PII; void Dijkstra(int x){ dis[x] = 0; priority_queue<PII,vector<PII>,greater<PII> > que; que.push({dis[x],x}); while(que.size()){ PII cur = que.top(); que.pop(); int u = cur.second; if(vis[u]) continue; vis[u] = 1; for(int i=head[u];~i;i = e[i].nex){ int v = e[i].v; int w = e[i].w; if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w; que.push({dis[v],v}); } } } } int main() { int _ = read; while(_ --) { itn n = read,m = read,l = read; init(); for(int i=1; i<=n; i++) a[i] = read; sort(a+1,a+1+n); int mx = a[n] - a[1]; for(int i=1; i<=m; i++) c[i] = read,v[i] = read; dp[0] = 0; for(int i=1; i<=m; i++) { for(int j=mx; j>=v[i]; j--) { dp[j] = min(dp[j], dp[j-v[i]] + c[i]); } } for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { if(i == j) add(i,j,0),add(j,i,0); else { if(dp[a[j]-a[i]] <= l) { add(i,j,1),add(j,i,1); } else add(i,j,0x3f3f3f3f),add(j,i,0x3f3f3f3f); } } } Dijkstra(1); if(dis[n] == 0x3f3f3f3f) puts("-1"); else cout << dis[n] << endl; } return 0; } /** 2 3 2 4 3 1 6 3 2 3 3 3 1 4 1 3 6 3 2 **/
L . Omar’s Bug [构造]
int findFirstGreaterThanOrEqual(int array[], int N, int X) { int start = 0, end = N; while (start < end) { int middle = (start + end) / 2; if (array[middle] > X) { end = middle; } else { start = middle + 1; } } return start; } int a[107]; int main() { int _ = read; while(_--) { int n = read, x = read, y = read; if(y == 1) {// dui if(x > n) { for(int i=1; i<=n; i++) { printf("%d%c",i,i==n?'\n':' '); } } else { for(int i=1; i<=n+1; i++) { if(i == x) continue; printf("%d%c",i,i==n+1?'\n':' '); } } } else { if(x <= n) { for(int i=1; i<=n; i++) { printf("%d%c",i,i==n?'\n':' '); } } else { for(int i=1; i<=n-1; i++) { printf("%d ",i); } cout << x << endl; } } } return 0; } /** **/
