multi4
题意：构造一个数组，求子矩阵前缀和。
思路：打表找规律，“发现”L为奇数时循环节为L，为偶数时循环节为2L，求相应循环节的二维前缀和然后加加减减计算一下就好。
虚伪地证明一下循环节：L为奇数时对于第x行/列开始的位置有（x + x+L-1）*L/2 -> (2x+L-1)/2（为整数）*L，因此扫过L行/列也就扫过了L整数倍"（2x+L-1）/2"倍的A[0]~A[L],即为一个循环节。
偶数则有（x + x+2L-1）*2L/2 -> (2x+2L -1) *L. (x+x+L-1)/2不是整数QAQ。。。
知道规律之后就是一个“简单”的模拟题了。
窝不仅憋了半天才写出来又憋了半天才过样例。
还因为赋值前就把偶数L乘二导致M数组值是错的WA掉。
还因为数组开小了（N=4*L）WA到怀疑人生。
都是oj的错。
为什么不是RE。
对。
就是oj的错。不是窝蠢。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long ll; 5 const int N = 40 + 5;///2L * 2!!!!!!!!!!!!!!!!!!!!!!!!!!!!!aaaaaaaaaaaaaaaaaaaaaaaaa!!!!!!!!!!!!!! 6 int T, l, A[N], q; 7 ll M[N][N]; 8 9 ll cal(int x, int y){ 10 return (1ll*(x/l)*1ll*(y/l)*M[l][l]) + (1ll*(x/l))*M[l][y%l] + (1ll*(y/l))*M[x%l][l]+ M[x%l][y%l]; 11 } 12 13 int main() 14 { 15 scanf("%d", &T); 16 while(T--){ 17 scanf("%d", &l); 18 for(int i = 0; i < l; i++) scanf("%d", &A[i]); 19 int L=l; 20 if(!(l&1)) l <<= 1; 21 int cursor = 0; 22 for (int i = 1; i < (l<<1); ++i) { 23 for (int j = 1; j <= i; ++j) { 24 M[j][i - j + 1] = 1ll*A[cursor]; 25 cursor = (cursor + 1) % L; 26 } 27 } 28 for(int i = 1; i <= l; i++){ 29 for(int j = 1; j <= l; j++){ 30 M[i][j] += M[i - 1][j] + M[i][j - 1] - M[i - 1][j - 1]; 31 } 32 } 33 int x0, y0, x1, y1; 34 scanf("%d", &q); 35 while(q--){ 36 scanf("%d %d %d %d", &x0, &y0, &x1, &y1); 37 x0++,y0++,x1++,y1++; 38 ll ans = cal(x1, y1) - cal(x0-1, y1) - cal(x1, y0-1) + cal(x0-1, y0-1); 39 printf("%lld\n", ans); 40 } 41 } 42 return 0; 43 }
http://acm.hdu.edu.cn/showproblem.php?pid=6341
题意：小天才的16*16数独被倒霉孩子逆时针转了几块，帮难过的她计算最少旋转次数。
思路：爆搜+可行性剪枝？
随便剪了一下不知道算不算可行性剪枝啊。。其实有点过于暴力了。
因为check的时候没有把之前处理过的的非当前行一起check导致WA。
当cnt>=ans就return（剪枝）。
x>16时才return一开始写错少判了一组。。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 16; 5 const int inf = 16 * 3; 6 int ans, G[N+5][N+5], tmp[5][5], vis[N+5]; 7 char g[N+5][N+5]; 8 9 void Rotate(int x, int id){ 10 for(int i = 1, gj = id*4+1; i <= 4 && gj <= id*4+4; i++, gj++){ 11 for(int j = 1, gi = x+3; j <= 4 && gi >= x; j++, gi--){ 12 tmp[i][j] = G[gi][gj]; 13 } 14 } 15 for(int i = 1, gi = x; i <= 4 && gi <= x+3; i++, gi++){ 16 for(int j = 1, gj = id*4+1; j <= 4 && gj <= id*4+4; j++, gj++){ 17 G[gi][gj] = tmp[i][j]; 18 } 19 } 20 } 21 bool sudokucheck(int x){ 22 for(int i = x; i < x+4; i++){ 23 memset(vis, 0, sizeof(vis)); 24 for(int j = 1; j <= N; j++){ 25 if(vis[G[i][j]]++)return false; 26 } 27 } 28 for(int i = 1; i <= N; i++){ 29 memset(vis, 0, sizeof(vis)); 30 for(int j = 1; j < x+4; j++){///j = 1 1 1!!!!!!!!!!!!!!!!!!!WA!!!!!!!!!!!! 31 if(vis[G[j][i]]++)return false; 32 } 33 } 34 return true; 35 } 36 void dfs(int x, int cnt){ 37 if(cnt >= ans) return;///cut!!! 38 if(x == 17){///17!!!! 39 ans = cnt; 40 return; 41 } 42 for(int i = 0; i <= 3; i++, Rotate(x, 0)){ 43 for(int j = 0; j <= 3; j++, Rotate(x, 1)){ 44 for(int k = 0; k <= 3; k++, Rotate(x, 2)){ 45 for(int l = 0; l <= 3; l++, Rotate(x, 3)){ 46 if(sudokucheck(x)) {///cutQAQ... 47 dfs(x + 4, cnt + i + j + k + l); 48 } 49 } 50 } 51 } 52 } 53 } 54 void stoi(){ 55 for(int i = 1; i <= N; i++){ 56 for(int j = 1; j <= N; j++){ 57 if(g[i][j] >= ‘0‘ && g[i][j] <= ‘9‘) G[i][j] = int(g[i][j]) - ‘0‘; 58 else G[i][j] = int(g[i][j]) - ‘A‘ + 10; 59 } 60 } 61 } 62 63 int main() 64 { 65 int T; 66 scanf("%d", &T); 67 getchar(); 68 while(T--){ 69 for(int i = 1; i <= N; i++) scanf("%s", g[i]+1); 70 stoi(); 71 ans = inf; 72 dfs(1, 0); 73 printf("%d\n", ans); 74 } 75 return 0; 76 }
附dls 15ms代码。。。
大概就是每次判一小块，然后只需check与此块相关的处理过的行和列，比上面那个zz暴力快了10倍。
#include<algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <math.h> #include <time.h> #include <vector> #include <bitset> #include <queue> #include <map> #include <set> using namespace std; char s[16][16],w[16][16]; int Ans; void Rot(int a,int b) { for(int i=0;i<4;i++) for(int j=0;j<4;j++) w[j][3-i]=s[a+i][b+j]; for(int i=0;i<4;i++) for(int j=0;j<4;j++) s[a+i][b+j]=w[i][j]; } int tot,vis[16]; bool check(int a,int b)///only check the lines that related to the block!!!15-31MS!!!!!!!!!! { for(int i=a;i<a+4;i++) { tot++; for(int j=0;j<b+4;j++) { if(vis[s[i][j]]==tot) return 0; vis[s[i][j]]=tot; } } for(int i=b;i<b+4;i++) { tot++; for(int j=0;j<a+4;j++) { if(vis[s[j][i]]==tot) return 0; vis[s[j][i]]=tot; } } return 1; } void dfs(int i,int j,int k) { if(i==4) { Ans=min(Ans,k);return; } if(k>=Ans) return; if(j==4) return dfs(i+1,0,k); for(int t=0;t<4;t++) { if(check(i*4,j*4)) dfs(i,j+1,k+t); Rot(i*4,j*4); } } void solve() { for(int i=0;i<16;i++) scanf(" %s",s[i]); for(int i=0;i<16;i++) for(int j=0;j<16;j++) if(s[i][j]<=‘9‘) s[i][j]-=‘0‘; else s[i][j]=s[i][j]-‘A‘+10; Ans=1000;dfs(0,0,0); cout<<Ans<<endl; } int main() { int t;cin>>t; while(t--) solve(); return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200000 + 5; struct planet{ ll x, y; int id; bool operator <(const planet& other)const{ if(x != other.x) return x < other.x; if(y != other.y) return y > other.y; return id < other.id; } }a[N], st[N];///stack bool nec[N];///necessary. ll cross(planet a, planet b){ return a.x * b.y - a.y * b.x;} planet operator - (planet a, planet b){return planet{a.x - b.x, a.y - b.y, 0};} bool check(planet a, planet b, planet c){ return cross(b - a, c - a) != 0;}///==0 -> collineation. int main() { int T, n; scanf("%d", &T); while(T--){ 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 + 2, a + n); //puts(""); //for(int i = 1; i<=n;i++)printf("%d %lld %lld\n", a[i].id, a[i].x, a[i].y); int top = 1;///end; st[1] = a[1]; for(int i = 2; i <= n; i++){ if(i > 1 && a[i].x == a[i - 1].x) continue;/// while(top >= 2 && (st[top].y - st[top - 1].y) * (a[i].x - st[top].x) < (a[i].y - st[top].y) * (st[top].x - st[top - 1].x)) top--;///grad(A, B) < grad(B, C) -> delete B(concave). st[++top] = a[i]; } nec[1] = nec[top] = true; for(int i = 2; i < top; i++) nec[i] = check(st[i - 1], st[i], st[i + 1]);///st check collineation. int ans[top]; for(int i = top; i; i--){ if(nec[i]) ans[i] = st[i].id; else ans[i] = min(st[i].id, ans[i + 1]);///lexicographical } for(int i = 1; i <= top; i++) if(ans[i] == st[i].id) printf("%d%c", ans[i], (i == top? ‘\n‘: ‘ ‘)); } return 0; }
8/2 multi4 E找规律+模拟，空间开小了然后一直WA。。。J爆搜check不严谨WA。。。multi3 G凸包判共线写错数组名？？？样例太好过.想哭jpg。
原文：https://www.cnblogs.com/curieorz/p/9410798.html
