杭电多校第三场

杭电多校第三场

---

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; }

---

2 Problem B. Cut The String

dp+ 回文字符串

---

3 C. Dynamic Graph Matching

戳这里C. Dynamic Graph Matching

4 D. Euler Function

欧拉函数的公式， ϕ(n)=pk−11(p1−1) ϕ ( n ) = p 1 k − 1 ( p 1 − 1 ) ∗pk−12∗(p2−1)... ∗ p 2 k − 1 ∗ ( p 2 − 1 ) . . . p是质数，如果p > 3 ,则欧拉函数值一定是合数 只有当p= 2,p= 3,才有可能出现时质数的情况，而且 指数k < 3 所以只有前几个数才有可能欧拉函数值是素数2，或者3，排除这几个，或者打表看一下就完了

5 E. Find The Submatrix

这不是我的菜，。。。。 有空补题，四边形不等式优化dp，瑟瑟发抖 ### F. Grab The Tree 假设Q选的异或 和是 A，T选的是B， AB=sum A B = s u m （sum是所有的异或和） 所以异或和是0 的时候，无论Q怎么选，结果都是A和B相等 当异或和不是0的时候Q只需要选择sum最高位不为零同样的值就行了，即sum最高位不为零，同样选一个a[i] 最高位和sum相同

G. Interstellar Travel

转化一下，求叉积最小，变成求面积最小，改成求凸包，然后凸包拐点必选，从这一个点到另一个拐点上的点排序，按照要求选一个字典序最小的出来

H. Monster Hunter

原来claris说的贪心是这种贪心，怕怕

I. Random Sequence

交给队友补了

J. Rectangle Radar Scanner

同上

K. Transport Construction

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

L. Visual Cube

这种模拟题，编程能力是硬伤啊，感觉自己写的还ok

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; }