A Quality-Adjusted Life-Year
签到
B Gwen’s Gift
C Forest for the Trees
gcd
const int maxn=5e5+7; const int inf=0x3f3f3f3f; ll n,m,t,p,q; ll a[2],b[2]; inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; } int main(){ ll x1,x2,y1,y2; n=read(); m=read(); x1=read(); y1=read(); x2=read(); y2=read(); t=gcd(n,m); if(t==1){ printf("Yes"); return 0; } p=n/t; q=m/t; if(x1<=p&&y1<=q){ if(x2>=n-p&&y2>=m-q){ printf("Yes"); return 0; } ll k=x2/p; if(x2%p!=0) k++; a[0]=k; k=y2/q; if(y2%q!=0) k++; k=min(k,a[0]); printf("No\n"); printf("%lld %lld",p*k,q*k); } else{ printf("No\n"); printf("%lld %lld",p,q); } }
D H-Index
签到 二分
vector<int> v; bool check(int x) { int cnt = 0; for (int i = v.size() - 1;i >= 0;i--) { if (v[i] >= x) cnt++; else { break; } } return cnt >= x; } int main() { int n; scanf("%d", &n); for (int i = 1;i <= n;i++) { int x; scanf("%d", &x); v.push_back(x); } sort(v.begin(), v.end()); int l = 0, r = 1e9; while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } cout << l; return 0; }
E Driving Lanes
dp
根据题意，我们知道在弯道的情况下，行走的路程是 s+c∗i，其中i ii表示的是处于第几道，当c 大于0的情况下，要使得i ii尽可能地小，在c 小于0的情况下，要使得i ii尽可能地大，按照贪心的情况，我们可以直接对应1 ,m所以开始可以考虑贪心，但是要注意在变道的过程中，在直线上行驶的过程中也会多产生一部分代价，所以说在这个过程中，不一定是两个极端的车道1,m更优，而可能是在中间某一个车道产生了最优解，所以这里就不能够在使用贪心来解决，这里我们应该考虑用dp
ac_code:
int n,m,kk,r; int a[2007]; int s[2007],c[2007]; int dp[307][307]; int main() { n = read,m = read,kk = read,r = read; r += kk; for(int i=1; i<=n; i++) a[i] = read; for(int i=1; i<n; i++) s[i]=read,c[i]=read; int ans = 0; Clear(dp,0); dp[0][1] = 1; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(dp[i-1][j] == 0) continue; int t = dp[i-1][j]; for(int k=1; k<=m; k++) { if(a[i] >= abs(k - j) * kk) { if(!dp[i][k]) dp[i][k] = t + abs(k - j) * r + a[i] - abs(k - j) * kk + s[i] + c[i] * k; else dp[i][k] = min(dp[i][k],t + abs(k - j) * r + a[i] - abs(k - j) * kk + s[i] + c[i] * k); // debug(dp[i][k]); } } } } cout << dp[n][1] - 1 << endl; return 0; } /** 4 3 5 2 10 10 10 10 4 -1 4 -1 4 1 ->51 4 3 5 2 10 10 10 10 10 -3 10 -3 10 1 ->61 **/
F Treasure Spotting
计算几何
重判没了
G Neighborhood Watch
问有多少条道路经过了给出的地点，其中起点和终点可以相同
typedef long long ll; int a[200010], R[200010]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1;i <= m;i++) { int x; scanf("%d", &x); a[x] = 1; } int idx = n + 1; for (int i = n;i >= 1;i--) { if (a[i] == 0) R[i] = idx; else idx = i; } ll res = 0; for (int i = 1;i <= n;i++) { if (a[i] == 1) res += n - i; else { if (R[i] != n + 1) { res += n - R[i] + 1; } } } res += m; printf("%lld", res); return 0; }
H Small Schedule
重判没了
I Mr. Plow King
贪心
ll cal(ll n,ll m) { ll ret = 0; while(m) { ll x = (n - 1) * (n - 2) >> 1; if(m > x) { ret += x + 1; m = x << 1,-- n; } else ret += m,-- n,-- m; } return ret; } int main() { ll n = read,m = read; ll ret = 0; cout << cal(n,m) << endl; return 0; } /** **/
J Rainbow Road Race
bfs
二进制
假如给每一个颜色一个标号为1<<x，其中x从1->6
这样一来，就可以转化为求最短路，终止的条件是经过的路径的颜色|（位运算或）之后，值为27-1，而在判断能不能走的时候也可以这样非常巧秒的判断能不能走
ac_code:
#define Clear(x,val) memset(x,val,sizeof x) ll a[maxn << 1]; struct node { int v,nex,w; int col; } e[maxn]; int cnt,head[maxn]; int get(char c) { if(c == 'R') return 1; if(c == 'O') return 2; if(c == 'Y') return 3; if(c == 'G') return 4; if(c == 'B') return 5; if(c == 'I') return 6; if(c == 'V') return 7; } bool vis[3007][307]; ll dis[3007][307]; void init() { cnt = 0; Clear(head,-1); } void add(int u,int v,int w,int col) { e[cnt].v = v; e[cnt].w = w; e[cnt].col = 1<<col; e[cnt].nex = head[u]; head[u] = cnt ++; } struct Node { int to; ll w; int col; friend bool operator<(Node a,Node b) { return a.w > b.w; } }; priority_queue<Node> que; int tot[3007][3007]; int main() { int n = read,m = read; init(); char col; for(int i=1; i<=m; i++) { int u = read,v = read,w = read; scanf("%c",&col); int c = get(col) - 1; add(u,v,w,c); add(v,u,w,c); } que.push({1,0,0});// node 1 the tent memset(dis,127 / 3,sizeof dis); ll ans = 0; int flag = 0; while(que.size()) { Node frt = que.top(); que.pop(); vis[frt.to][frt.col] = true; if(frt.col == (1 << 7) - 1 && frt.to == 1) { ans = frt.w; flag = 1; break; } int u = frt.to; for(int i=head[u]; ~i; i=e[i].nex) { int to = e[i].v; int w = e[i].w; int col = e[i].col; int jue = col | frt.col; if(vis[to][jue]) continue;// conted with node1 if(w + frt.w < dis[to][jue]) { dis[to][jue] = w + frt.w; que.push({to,w + frt.w,jue}); } } } assert(flag); cout << ans << endl; return 0; } /** 7 7 1 2 1 R 2 3 1 O 3 4 1 Y 4 5 1 G 5 6 1 B 6 7 1 I 1 7 1 V 8 7 1 2 1 R 1 3 1 O 1 4 1 Y 1 5 1 G 1 6 1 B 1 7 1 I 1 8 1 V **/
