### 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

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