# 杭电多校第三场

xiaoxiao2021-03-01  15

### 6319 Problem A. Ascending Rating

int a[maxn], b[maxn], deq[maxn],c[maxn]; void solve(int n,int k){ int s = 1,t = 1; for(int i = n;i >= 1; --i){ while( s < t&& a[deq[t-1]] <= a[i]){ t--; } deq[t++] = i; if(n-i+1 >= k){ b[i] = a[deq[s]]; c[i] = t-s; if(deq[s] >= i+k-1){ s++; } } } } int main(void) { int T; scanf("%d",&T); while(T--){ int n,m,k,p,q,r,MOD; 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*a[i-1]*p+1LL*q*i+r)%MOD; solve(n,m); LL A = 0,B = 0; for(int i = 1;i <= n-m+1; ++i){ A += (b[i]^i); B += (c[i]^i); } printf("%lld %lld\n",A,B); } return 0; }

dp+ 回文字符串

### K. Transport Construction

Boruvka 算法不知道，只知道prim和kruskul，我可能需要回炉重造了

### L. Visual Cube

const int maxn = 100; char M[100][100]; int n,m; // 打印函数 void Print(int n,int m){ //cout<<n<<" "<<m<<endl; for(int i = 1;i <= n; ++i){ for(int j = 1;j <= m; ++j) putchar(M[i][j]); puts(""); } } // 前面 void D1(int a,int b,int c){ int aa = b*2; int bb = 1; for(int i = 1;i <= c*2+1; ++i){ for(int j = 1;j <= 2*a+1; ++j){ if(i % 2 == 0){ if( j % 2 == 0) M[i+aa][j] = '.'; else M[i+aa][j] = '|'; } else { if(j % 2 == 0) M[i+aa][j] = '-'; else M[i+aa][j] = '+'; } } } } // 上面 void D2(int a,int b,int c){ for(int i = 1;i <= b*2; ++i){ for(int j = 1; j <= 2*a+1; ++j){ int jj = 2*b-i+j+1; if(i% 2==0){ if(jj % 2==0) M[i][jj] = '/'; else M[i][jj] = '.'; } else { if(jj % 2==0) M[i][jj] = '-'; else M[i][jj] = '+'; } } } } // 下面 void D3(int a,int b,int c){ for(int j = 1;j <= 2*b+1; ++j){ for(int i = 1;i <= 2*c+1;++i){ int jj = j + 2*a; int ii = i + 2*b+1-j; if(j % 2 == 0){ if(i % 2==0) M[ii][jj] = '.'; else M[ii][jj] = '/'; } else { if(i % 2==0) M[ii][jj] = '|'; else M[ii][jj] = '+'; } } } } void Draw(int a,int b,int c){ D1(a,b,c); D2(a,b,c); D3(a,b,c); } int main(void) { int T; scanf("%d",&T); int a,b,c; while(T--){ scanf("%d %d %d",&a,&b,&c);// 初始化 for(int i = 1;i < maxn; ++i) for(int j = 1;j < maxn; ++j) M[i][j] = '.'; n = 2*b+2*c+1;// n和m是二维图的长和宽 m = 2*a+2*b+1; Draw(a,b,c); Print(2*b+2*c+1,2*a+2*b+1); } return 0; }