Problem A. Ascending Rating

---

给出n长，每个区间长为m，给出前k个数。求每个区间内权值递增的个数^i和更改最大值的次数^i。

---

从后往前，维护单调队列。

---

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
#define ll long long
const int N = 1e7+5;
int T, n, m, k, p, q, r, mod;
ll A, B;
int h, t, idx[N];
int a[N];

int main()
{
    scanf("%d", &T);
    while(T --){
        scanf("%d%d%d%d%d%d%d", &n, &m, &k, &p, &q, &r, &mod);
        for(int i=1; i<=k; i++){
            scanf("%d", &a[i]);
        }
        for(int i=k+1; i<=n; i++){
            a[i] = (1ll*p*a[i-1]+1ll*q*i+r)%mod;//1ll减少mod次数
        }
        h = 1, t = 0;
        A = B = 0;
        for(int i=n; i>=1; i--){
            while(h<=t && a[idx[t]]<=a[i]) t --;///
            idx[++t] = i;//末尾放值
            if(i <= n-m+1){//开始满足一个区间后更新
                while(idx[h] >= i+m) h++;//头结点不在区间内
                A += a[idx[h]]^i;
                B += (t-h+1)^i;
            }
        }
        printf("%lld %lld\n", A, B);
    }
    return 0;
}

Problem G. Interstellar Travel
参考自

---

cost=xi×yj−xj×yi
=> 向量(xi,yi)与(xj,yj)的叉积
=> (xi,yi),(xj,yj),(0,0)构成的三角形的有向面积的2倍
(熟悉这个的话,熟悉这个的话,熟悉这个的话……)
得出从这n个点中选出一些点构成一个上半凸包是最优的。

---

字典序尽可能小
三点以上共线，判断两端点间的点是否能使得字典序更小，决定是否选中

---

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 2e5+5;
int t, n, cnt;
int ans[N], vis[N];
struct Point{
    ll x, y, id;
}a[N], p[N];
bool cmp(Point A, Point B)
{
    if(A.x != B.x) return A.x < B.x;
    if(A.y != B.y) return A.y > B.y;
    return A.id < B.id;
}
Point operator-(Point A, Point B) { return (Point){A.x-B.x, A.y-B.y, 0};}//运算符重载
ll cross(Point A, Point B) { return A.x*B.y - A.y*B.x; }//叉积
int check(Point A, Point B, Point C) { return cross(B-A,C-A) != 0; }//两直线不平行

int main()
{
    scanf("%d", &t);
    while(t --){
        cnt = 0;
        memset(ans, 0, sizeof(ans));
        memset(vis, 0, sizeof(vis));
        scanf("%d", &n);
        for(int i=1; i<=n; i++){
            scanf("%lld%lld", &a[i].x, &a[i].y);
            a[i].id = i;
        }
        sort(a+1, a+n+1, cmp);
        for(int i=1; i<=n; i++){
            if(i>1 && a[i].x==a[i-1].x) continue;//x相同的点，前面的y越大
            while(cnt>=2 && (p[cnt].y-p[cnt-1].y)*(a[i].x-p[cnt].x) < (p[cnt].x-p[cnt-1].x)*(a[i].y-p[cnt].y))//根据极角大小判断之前的点是否能被选中
                cnt --;
            p[++cnt] = a[i];
        }
        vis[1] = vis[cnt] = 1;///cnt
        for(int i=2; i<cnt; i++) vis[i] = check(p[i-1], p[i], p[i+1]);//是否在同一直线上
        for(int i=cnt; i>=1; i--){///cnt
            if(vis[i]) ans[i] = p[i].id;
            else ans[i] = min((int)p[i].id, ans[i+1]);//字典序小
        }
        for(int i=1; i<=cnt; i++){
            if(ans[i] == p[i].id)
                printf("%d%c", ans[i], i==cnt? '\n':' ');///
        }
    }
    return 0;
}

Problem L. Visual Cube

---

给出长宽高（a,b,c），按照样例格式输出立方体。

---

刚开始的想法，分成上中下三部分来模拟

开始过不去这种两边阴影在同一行的立方体

最后，大致分成三个部分来写

---

签到题写成这样，服了

---

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100;///50 TLE
int t, a, b, c;
char g[N][N];

int main()
{
    scanf("%d", &t);
    while(t --){
        memset(g, ' ', sizeof(g));
        scanf("%d%d%d", &a, &b, &c);
        int i, j, k;
        int h = 2*(b+c)+1;//整个图的高
        int r = 2*(a+b)+1;//整个图的宽

        for(i=0; i<2*b; i++){
            for(j=0; j<2*b-i; j++){//左上角阴影
                g[i][j] = '.';
            }
            for(k=j; k<r-i; k++){//顶层的区域
                if(i%2) g[i][k] = k%2? '/':'.';
                else g[i][k] = k%2? '-':'+';
            }
        }

        for(k=2*b; k<2*(b+c)+1; k++){//中部（正面）
            for(j=0; j<2*a+1; j++){
                if(k%2) g[k][j] = j%2? '.':'|';
                else g[k][j] = j%2? '-':'+';
            }
        }
        ///min(h-2*b,2*b)
        for(k=0; k<h; k++){//右边阴影和侧面
            for(j=max(r-k,2*a+1); j<r; j++){
                if(h-k > j-2*a){///
                    if(k%2) g[k][j] = j%2? '/':'|';
                    else g[k][j] = j%2? '.':'+';
                }
                else
                    g[k][j] = '.';
            }
        }

        for(i=0; i<h; i++){
            for(j=0; j<r; j++){
                printf("%c", g[i][j]);
            }printf("\n");
        }
//        printf("\n");///PE
    }
    return 0;
}