A 

思路: dp水题

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int MOD = 1e9 + 7, N = 1e6 + 5;LL dp[N];int main() {    int T, n;    dp[0] = 1;    for (int i = 1; i < N; i++) {        for (int j = max(0, i-8); j < i; j++) dp[i] = (dp[i] + dp[j]) % MOD;    }    scanf("%d", &T);    for (int i = 1; i <= T; i++) {        scanf("%d", &n);        printf("%lld\n", dp[n/3]);    }    return 0;}
          
         
        
       
      

 

B 

思路:用set

n^2logn暴力枚举

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 2e3 + 5;pair
           
             a[N];multiset
            
              s1;multiset
             
               s2;int main() { int n, k; scanf("%d %d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d %d %d", &a[i].fi, &a[i].se.fi, &a[i].se.se); sort(a+1, a+1+n); LL ans = 1e16; for (int i = 1; i <= n; i++) { s1.insert(a[i].se); if(i >= k) { s2.clear(); for (auto it : s1) { s2.insert(it.se); if(s2.size() > k) s2.erase(--s2.end()); if(s2.size() == k) { ans = min(ans, 1LL*a[i].fi + 1LL*it.fi + 1LL*(*--s2.end())); } } } } printf("%lld\n", ans); return 0;}
             
            
           
          
         
        
       
      

 

C 

思路:水题, 减S取模

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e3 + 10;char s[N];bool isAlphaBete(char c){    return c>='A'&&c<='Z'||c>='a'&&c<='z';}int main() {    int n, S;    scanf("%d %d", &n, &S);    S %= 26;    char c;    c = getchar();    while((c = getchar())!=EOF){        if(isupper(c)) {            int t = c - 'A';            t = (t + 26 - S) % 26;            c = 'A' + t;        }        else if(islower(c)) {            int t = c - 'a';            t = (t + 26 - S) % 26;            c = 'a' + t;        }        putchar(c);    }    return 0;}
          
         
        
       
      

 

D 

思路:贪心

假设相邻两个元素a, b, 在此之前的大象的体重为w

那么按a前b后的顺序的花费是 w*a.c + w*a.r*b.c

按b前a后的顺序的花费是 w*b.c + w*b.r*a.c

无论什么顺序,经过这两个元素后大象的体重都是w*a.r*b.r

那么a在b前的条件是w*a.c + w*a.r*b.c < w*b.c + w*b.r*a.c

即 a.c + a.r*b.c < b.c + b.r*a.c

按这个条件写个cmp函数排个序即可

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e5 + 10;const LL INF = (1ll<<60);struct node {    int c;    double r;}a[N];int n, w;bool cmp(node a, node b) {    return  a.c + b.c*a.r < b.c + a.c*b.r;}void solve() {    double ans = INF;    sort(a+1, a+1+n, cmp);    double tw = w, tans = 0;    for (int i = 1; i <= n; i++) {        tans += tw * a[i].c;        tw *= a[i].r;    }    ans = min(ans, tans);    printf("%.10f\n", ans);}int main() {    scanf("%d %d", &n, &w);    for (int i = 1; i <= n; i++) scanf("%d %lf", &a[i].c, &a[i].r);    solve();    return 0;}
          
         
        
       
      

 

E 

思路:一个向量旋转乘以下面的旋转矩阵即可(Θ > 0 表示逆时针)

然后多边形旋转的话就一个点不动,其他点绕改点旋转

旋转好后将多边形左下角移动到与x轴正半轴和y正半轴相切,然后按w*h等比例缩放

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e5 + 5;const int INF = 0x7f7f7f7f;const double eps = 1e-8;//考虑误差的加法double add(double a, double b) {    if(fabs(a + b) < eps * (fabs(a) + fabs(b))) return 0;    return a + b;}//考虑误差的与0比较int dcmp(double x) {    if(fabs(x) < eps) return 0;    else return x<0?-1:1;}struct P {    double x, y;    P(){}    P(double x, double y) :x(x), y(y){}    bool operator == (P p) {        return dcmp(x - p.x) == 0 && dcmp(y - p.y) == 0;    }    P operator + (P p) {        return P(add(x, p.x), add(y, p.y));    }    P operator - (P p) {        return P(add(x, -p.x), add(y, -p.y));    }    P operator * (double p) {        return P(x * p, y * p);    }    P operator / (double p) {        return P(x / p, y / p);    }    //点积    double dot(P p) {        return add(x * p.x, y * p.y);    }    //叉积    double cross(P p) {        return add(x * p.y, -y * p.x);    }}p[N];typedef P Vector;//向量逆时针旋转Vector Rotate(Vector a,double rad)  {    return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad));}int main() {    int a, w, h, n;    scanf("%d %d %d %d", &a, &w, &h, &n);    double A = a*pi/180;    for (int i = 1; i <= n; i++) scanf("%lf %lf", &p[i].x, &p[i].y);    for (int i = 2; i <= n; i++) p[i] = p[1] + Rotate(p[i] - p[1], A);    double mnx = INF, mny = INF;    for (int i = 1; i <= n; i++) mnx = min(mnx, p[i].x), mny = min(mny, p[i].y);    for (int i = 1; i <= n; i++) p[i].x -= mnx, p[i].y -= mny;    double mxx = 0, mxy = 0;    for (int i = 1; i <= n; i++) mxx = max(mxx, p[i].x), mxy = max(mxy, p[i].y);    for (int i = 1; i <= n; i++) p[i].x = p[i].x*w/mxx, p[i].y = p[i].y*h/mxy;    for (int i = 1; i <= n; i++) printf("%.10f %.10f\n", p[i].x, p[i].y);    return 0;}
          
         
        
       
      

 

F 

思路:首先将给的小数乘以10000得到式子 d / 100000 中的 d, 然后10000/gcd(10000, d) 就是答案

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headchar s[105];int main() {    int T;    scanf("%d", &T);    for (int i = 1; i <= T; i++) {        scanf("%s", s);        int n = strlen(s);        int t = 0;        for (int i = 2; i < n; i++) {            t = t*10 + s[i] - '0';        }        for (int i = n; i < 6; i++) {            t = t*10;        }        int d = __gcd(t, 10000);        printf("%d\n", 10000/d);    }    return 0;}
          
         
        
       
      

 

G 

思路:水题, (a*d*f + c*b*f + e*b*d) / (b*d*f) 约分后即是答案

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headint main() {    int T;    LL a, b, c, d, e, f;    scanf("%d", &T);    for (int i = 1; i <= T; i++) {        scanf("%lld/%lld %lld/%lld %lld/%lld", &a, &b, &c, &d, &e, &f);        LL up = a*d*f + c*b*f + e*b*d;        LL down = b*d*f;        LL d = __gcd(up, down);        up /= d;        down /= d;        printf("%lld/%lld\n", up, down);    }    return 0;}
          
         
        
       
      

 

H 

思路:水题, 题意难懂, 把a drink理解为一瓶酒

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int MOD = 1e9 + 7, N = 1e6 + 5;LL dp[N];int main() {    int T, n, k;    scanf("%d", &T);    for (int i = 1; i <= T; i++) {        scanf("%d %d", &n, &k);        int b = n*(n+1)/2;        if(k < b) puts("Too drunk to count");        else if((k-b) %  n == 0) printf("%d\n", n+1+(k-b)/n);        else puts("Too drunk to count");    }    return 0;}
          
         
        
       
      

 

I 

思路: 最大流, 要拆点

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 2e3 + 5, M = 6e3 + 10;const int INF = 0x3f3f3f3f;pii a[N];piii b[N];struct edge {    int to, cap, rev;};vector
           
             g[M];int level[M], iter[M], mxv = 0;void add_edge(int from, int to, int cap) { g[from].pb({to, cap, g[to].size()}); g[to].pb({ from, 0, g[from].size()-1});}void bfs(int s) { for (int i = 0; i <= mxv; i++) level[i] = -1; queue
            
              q; level[s] = 0; q.push(s); while(!q.empty()) { int v = q.front(); q.pop(); for (edge &e : g[v]) { if(e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } }}int dfs(int v, int t, int f) { if (v == t) return f; for (int &i = iter[v]; i < g[v].size(); i++) { edge &e = g[v][i]; if(e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; } } } return 0;}int max_flow(int s, int t) { int flow = 0; for(;;) { bfs(s); if(level[t] < 0) return flow; for (int i = 0; i <= mxv; i++) iter[i] = 0; int f; while((f = dfs(s, t, INF)) > 0) { flow += f; } }}int main() { int n, m; LL s; scanf("%d %d %lld", &n, &m, &s); if(s < 10) return 0*puts("NO"); s -= 10; for (int i = 1; i <= n; i++) scanf("%d %d", &a[i].fi, &a[i].se); for (int i = 1; i <= m; i++) scanf("%d %d %d", &b[i].fi.fi, &b[i].fi.se, &b[i].se); int st = 0; for (int i = 1; i <= n; i++) add_edge(st, i, 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int dx = abs(b[j].fi.fi - a[i].fi), dy = abs(b[j].fi.se - a[i].se); if(1ULL*dx*dx + 1ULL*dy*dy <= 1ULL*s*s) { add_edge(i, n+j, 1); } } } for (int i = 1; i <= m; i++) { add_edge(i+n, i+n+m, b[i].se); } mxv = m+n+m+1; for (int i = 1; i <= m; i++) { add_edge(i+n+m, mxv, INF); } if(max_flow(st, mxv) == n) puts("YES"); else puts("NO"); return 0;}
            
           
          
         
        
       
      

 

J 

思路:线段树, 用long double

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e5 + 5;const long double up = pow((long double)2.0, 100);long double tree[N<<2];void push_up(int rt) {    tree[rt] = tree[rt<<1] * tree[rt<<1|1];}void build(int rt, int l, int r) {    if(l == r) {        cin >> tree[rt];        return ;    }    int m = l+r >> 1;    build(ls);    build(rs);    push_up(rt);}void update(int p, double x, int rt, int l, int r) {    if(l == r) {        tree[rt] = (long double)x;        return ;    }    int m = l+r >> 1;    if(p <= m) update(p, x, ls);    else update(p, x, rs);    push_up(rt);}long double query(int L, int R, int rt, int l, int r) {    if(L <= l && r <= R) return tree[rt];    int m = l+r >> 1;    long double ans = 1;    if(L <= m) ans *= query(L, R, ls);    if(R > m) ans *= query(L, R, rs);    return ans;}int main() {    int n;    scanf("%d", &n);    build(1, 1, n);    int q, ty, l, r, x;    double p;    scanf("%d", &q);    for (int i = 1; i <= q; i++) {        scanf("%d", &ty);        if(ty == 1) {            scanf("%d %lf", &x, &p);            update(x, p, 1, 1, n);        }        else {            scanf("%d %d", &l, &r);            long double t = query(l, r, 1, 1, n);            if(t >= up) printf("INFINITE!\n");            else cout << fixed << setprecision(10) << t << '\n';        }    }    return 0;}