# POJ 3061 Sequence

## code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  #include #include using namespace std; const int maxn = 1e5+7; int a[maxn]; int main() { int t; scanf("%d", &t); while (t--) { int n, S, tot = 0; scanf("%d%d", &n, &S); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); tot += a[i]; } if (tot <= S) { printf("%d\n", tot == S ? n : 0); continue; } int l = 0, r = 0; //初始化尺子 int sum = 0; // 初始化尺子长度存的信息 int res = n + 1; //初始化答案inf=n+1 while (1) {// 尺子不断向右推直到从某个左端起最大能取到的和小于S while (r <= n && sum < S) //推尺子右端到满足题意 sum += a[r++]; if (sum < S) break; res = min(res, r - l); // r已经加过1 sum -= a[l++]; //推尺子左端一格，同时更新sum } printf("%d\n", res > n ? 0 : res); } } 

# HDU 5672 String

## code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32  #include using namespace std; const int maxn = 1e6+7; typedef long long ll; #define clr(a,b) memset(a,b,sizeof(a)) char str[maxn]; int vis[27]; int main() { int t; scanf("%d", &t); while (t--) { clr(vis, 0); int k; scanf("%s %d", str, &k); int len = strlen(str); ll ans = 0; int l = 0, r = 0; int sum = 0; for (;;) { while (r < len && sum < k) { int cur = str[r++] - 'a'; if (!vis[cur]) sum++; vis[cur]++; } if (sum < k) break; //从某个左端点取遍也不足k个相异字符,推出 ans += len - (r - 1);// 此处r++后减掉但因为0-base不用再+1 int cur = str[l++] - 'a'; vis[cur]--; if (!vis[cur]) sum--; } printf("%lld\n", ans); } } 

# POJ 3320 Jessica’s Reading Problem

## trick

尺取+map映射+set，$O(n)$，细节看代码

## code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25  #include using namespace std; const int maxn = 1e6+7; int a[maxn]; int main() { int p;scanf("%d",&p); set all; for(int i=0;i cnt; //cnt[知识点]=次数 int sum = 0; int l = 0, r = 0; int res = p; for(;;) { while(sum < n && r < p) if(!cnt[a[r++]]++) sum ++; //该知识点第一次出现 if(sum < n) break; res = min(res, r-l); if(!--cnt[a[l++]]) sum--; //右移1位导致该知识点不出现更新sum } return !printf("%d\n",res); } 

# HDU 1937 Finding Seats

## code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32  #include using namespace std; const int maxn = 333; int mp[maxn][maxn], sum[maxn][maxn]; char str[maxn]; const int inf = 0x3f3f3f3f; int main() { int k, r, c; while (scanf("%d%d%d", &r, &c, &k) != EOF&&r+c+k) { memset(sum, 0, sizeof(sum)); for (int i = 1; i <= r; i++) { scanf("%s", str + 1); for (int j = 1; j <= c; j++) { mp[i][j] = str[j] == '.'; sum[i][j] += sum[i][j - 1] + mp[i][j]; } } for (int i = 2; i <= r; i++) for (int j = 1; j <= c; j++) sum[i][j] += sum[i - 1][j]; //打完前缀和 int ans = inf; for (int i = 1; i <= c; i++) for (int j = i; j <= c; j++) {// 枚举第i列到第j列 int p = 1; //行游标 for (int t = p; t <= r; t++) { while(sum[t][j]-sum[t][i-1]-sum[p-1][j]+sum[p-1][i-1]>=k) ans = min(ans, (j - i + 1) * (t - p + 1)), p++; } } printf("%d\n",ans); } } 

# HDU 6103 Kirinriki

## code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37  #include using namespace std; const int maxn = 5005; char str[maxn]; int ans; void solve(int len, int limit) { for (int i = 2; i <= len; i++) { //遍历右端点，取等号便于处理奇偶mid int mid = (i >> 1); int l = 0, r = 0; int sum = 0; for (int j = 0; j < mid; j++) {//遍历左端点 sum += abs(str[j] - str[i - j - 1]); if (sum <= limit) r++, ans = max(ans, r); else { //相同长度平移 r--; sum -= abs(str[j] - str[i - j - 1]); //还原状态 减掉当前的j sum -= abs(str[l] - str[i - l - 1]);// 减去当前的l l++, j--; //移动左端点，下一时刻相当于平移 } } } } int main() { int t; scanf("%d", &t); while (t--) { int m; scanf("%d %s", &m, str); ans = 0; int len = strlen(str); solve(len, m); strrev(str); //正反各跑一遍 solve(len, m); printf("%d\n", ans); } }