### POJ 3061 Sequence

#### code

#include <cstdio>
#include <algorithm>
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

#include <bits/stdc++.h>
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 #### 题意 给出$P(1e6)$页书，每页包含一个知识点，求一段长度最小的连续的区间使得包含所有的知识点。 #### trick 尺取+map映射+set，$O(n)$，细节看代码 #### code #include<bits/stdc++.h> using namespace std; const int maxn = 1e6+7; int a[maxn]; int main() { int p;scanf("%d",&p); set<int> all; for(int i=0;i<p;i++) { scanf("%d",&a[i]); all.insert(a[i]); } int n = all.size(); map<int,int> 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

$#include <bits/stdc++.h> 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

#include <bits/stdc++.h>
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);
}
}


This site uses Akismet to reduce spam. Learn how your comment data is processed.