1003
三个人一起乱搞了两个小时才搞出来。
wjh 写了一个二分答案后一直在调质数的范围，但是就是卡不过去。
对拍了半天也没拍出来错误。
结束前半个小时，我猜想既然数据随机，那么质数最大值大概也在 $\frac{n}{k}$ 附近，于是把质数枚举到了 $\frac{n}{k}$ 的后 $10$ 个质数，发现 5796ms 极限卡了过去！
贴一个赛时代码。
代码（赛时）
#include<bits/stdc++.h>
using namespace std;
int T;
int n, k;
int a[250010];
int sum[200010];
int f[200010];
int pr[200010];
int cnt;
inline int read() {
int w=1,x=0;
char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return w*x;
}
bool check (int x) {
for (int i = 1; i <= n; i ++) {
f[i] = f[i - 1];
int id=-1;
for (int j = 1; j <= cnt && i >= pr[j] && pr[j] <= n/k ; j ++) {
if (sum[i] - sum[i - pr[j]] >= x) f[i] = max(f[i], f[i - pr[j]] + 1);
id=j;
}
if(id!=-1&&id<=cnt&&i>=pr[id]) {
for(int j=id+1;j<=cnt && i>= pr [j] && j<=id+10 ;j++) {
if (sum[i] - sum[i - pr[j]] >= x) f[i] = max(f[i], f[i - pr[j]] + 1);
}
}
if (f[i] >= k) return true;
}
return false;
}
int v[200010];
void primes(int n) {
for(int i=2;i<=n;i++) {
if(!v[i]) pr[++cnt]=i,v[i]=i;
for(int j=1;j<=cnt;j++) {
if(pr[j]>v[i]||i*pr[j]>n) break;
v[i*pr[j]]=pr[j];
}
}
}
int main() {
primes(22000);
T=read();
while (T --) {
n=read(),k=read();
int L = 0, R = 0;
for (int i = 1; i <= n; i ++) {
a[i]=read();
sum[i] = sum[i - 1] + a[i];
if (a[i] < 0) L += a[i];
if (a[i] > 0) R += a[i];
}
if (k * 2 > n) {
cout << "impossible" << endl;
continue;
}
while (L < R) {
int mid = (L + R + 1) >> 1;
if (check(mid))
L = mid;
else R = mid - 1;
}
cout << L << endl;
}
return 0;
}1005
签到题，模拟。
wjh 写的。
贴个他代码。
代码（赛时）
#include <bits/stdc++.h>
using namespace std;
int T;
int n, m, hp, dmg;
char c[60][900];
int main () {
cin >> T;
while (T --) {
cin >> n >> m >> hp >> dmg;
if (dmg > m) dmg = m;
c[0][0] = c[0][m + 1] = c[n + 1][0] = c[n + 1][m + 1] = '+';
for (int i = 1; i <= n; i ++)
c[i][0] = c[i][m + 1] = '|';
for (int i = 1; i <= m; i ++)
c[0][i] = c[n + 1][i] = '-';
int num = hp / m;
int now;
if (hp % m == 0) {
char co = 'A' + (num - 1) % 5;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
c[i][j] = co;
now = m;
} else {
char co1 = 'A' + (num - 1) % 5;
if (num == 0) co1 = ' ';
char co2 = 'A' + (num) % 5;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= hp % m; j ++)
c[i][j] = co2;
for (int j = hp % m + 1; j <= m; j ++)
c[i][j] = co1;
}
now = hp % m;
}
while (dmg --) {
for (int i = 1; i <= n; i ++)
c[i][now] = '.';
now --;
if (now == 0) now = m;
}
for (int i = 0; i <= n + 1; i ++) {
for (int j = 0; j <= m + 1; j ++)
cout << c[i][j];
cout << endl;
}
}
return 0;
}1007
wjh 和 hx 看的题。
贴个赛时代码。
代码（赛时）
#include <bits/stdc++.h>
using namespace std;
int T;
int a[250010];
struct Node {
int num;
int id;
} b[250010];
bool cmp (Node x, Node y) {
return x.num > y.num;
}
int n, m;
int x;
int amin;
long long sum;
void findmin() {
amin = INT_MAX;
for (int i = 0; i < n; i ++)
if (a[i] < amin) amin = a[i];
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T --) {
cin >> n >> m;
sum = 0;
for (int i = 0; i < n; i ++) {
cin >> a[i];
sum += a[i];
}
findmin();
for (int i = 0; i < n; i ++) {
cin >> b[i].num;
b[i].id = i;
}
sort (b, b + n, cmp);
while (m --) {
cin >> x;
bool flag = 0;
for (int i = 0; i < n; i ++) {
if (b[i].num <= amin) break;
int pos = (b[i].id - x + n) % n;
if (a[pos] == amin) flag = 1;
if (a[pos] < b[i].num) {
sum -= a[pos];
sum += b[i].num;
a[pos] = b[i].num;
}
}
if (flag) findmin();
cout << sum << endl;
}
}
return 0;
}1009
发现可以把每个字母出现的位置存起来，然后二分来找每个名字出现完的第一个位置 $pos_i$ 。
同理，把每个数字出现的位置存起来，然后二分倒着来找每个日期出现的最后一个位置，并依此来统计 $f_i$ 表示 $i\sim n$ 内本质不同的日期的数量。
于是答案即为
代码（赛时）
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int T;
int n,m;
string s;
int pos[30][N],posn[15][N];
string name[N];
string date[410];
int ds[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int ans;
int f[N],g[N];
string getstring(int x) {
string res="";
if(x<10) {
res+=(char)('0'+x);
res='0'+res;
}
else if(x<20) {
res+=(char)('0'+x-10);
res='1'+res;
}
else if(x<30) {
res+=(char)('0'+x-20);
res='2'+res;
}
else {
res+=(char)('0'+x-30);
res='3'+res;
}
return res;
}
int tot=0;
void init() {
for(int i=1;i<=12;i++) {
string m=getstring(i);
for(int j=1;j<=ds[i];j++) {
string d=getstring(j);
date[++tot]=m+d;
}
}
}
int zcnt[30],ncnt[15],pp[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
init();
cin>>T;
while(T--) {
ans=0;
cin>>n>>m;
cin>>s;
s=' '+s;
for(int i=1;i<=n;i++) cin>>name[i];
for(int i=1;i<=m;i++) {
if(s[i]>='a'&&s[i]<='z') pos[s[i]-'a'][++zcnt[s[i]-'a']]=i;
else posn[s[i]-'0'][++ncnt[s[i]-'0']]=i;
}
for(int i=0;i<10;i++) reverse(posn[i]+1,posn[i]+ncnt[i]+1);
for(int i=1;i<=n;i++) {
bool flag=true;;
int sz=name[i].size(),last=0;
for(int j=0;j<sz;j++) {
int l=1,r=zcnt[name[i][j]-'a'];
while(l<r) {
int mid=(l+r)/2;
if(pos[name[i][j]-'a'][mid]>last) r=mid;
else l=mid+1;
}
if(pos[name[i][j]-'a'][r]<=last) {
flag=false;
break;
}
last=pos[name[i][j]-'a'][r];
}
if(flag) pp[i]=last;
else pp[i]=m+1;
}
for(int i=1;i<=tot;i++) {
bool flag=true;
int sz=date[i].size(),last=m+1;
for(int j=sz-1;j>=0;j--) {
int l=1,r=ncnt[date[i][j]-'0'];
while(l<r) {
int mid=(l+r)/2;
if(posn[date[i][j]-'0'][mid]<last) r=mid;
else l=mid+1;
}
if(posn[date[i][j]-'0'][r]>=last) {
flag=false;
break;
}
last=posn[date[i][j]-'0'][r];
}
if(flag) g[last]++;
}
for(int i=m;i>=1;i--) g[i]+=g[i+1];
for(int i=1;i<=n;i++) ans+=g[pp[i]+1];
cout<<ans<<endl;
for(int i=0;i<26;i++) zcnt[i]=0;
for(int i=1;i<=n;i++) pp[i]=0;
for(int i=0;i<10;i++) ncnt[i]=0;
for(int i=1;i<=m;i++) g[i]=0;
}
return 0;
}
