| Solved | A | Gym 100712A | Who Is The Winner | |
| Solved | B | Gym 100712B | Rock-Paper-Scissors | |
| Solved | C | Gym 100712C | Street Lamps | |
| Solved | D | Gym 100712D | Alternating Strings | |
| Solved | E | Gym 100712E | Epic Professor | |
| Solved | F | Gym 100712F | Travelling Salesman | |
| Solved | G | Gym 100712G | Heavy Coins | |
| Solved | H | Gym 100712H | Bridges | |
| Solved | I | Gym 100712I | Bahosain and Digits | |
| Solved | J | Gym 100712J | Candy | |
| Solved | K | Gym 100712K | Runtime Error | |
| Solved | L | Gym 100712L | Alternating Strings II |
2015 ACM Amman Collegiate Programming Contes
训练赛01,icpc赛制五小时,难度三星,最终AC:8/12 打得很菜
A 找到最高分数同时罚时最小的就行
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=1e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
struct node {
int a,b;
string name;
}x[maxn];
int cmp(node a,node b){
if(a.a==b.a) return a.b<b.b;
else return a.a>b.a;
}
int main(){
// #define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
// memset(x,0,sizeof x);
read(n);
for(int i=;i<n;i++){
cin>>x[i].name>>x[i].a>>x[i].b;
}
sort(x,x+n,cmp);
cout<<x[].name<<endl;
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
B 先预处理前缀和,再枚举2个分界点,复杂度n^2
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=2e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
int num[maxn];
char s[maxn];
int s1[maxn],s2[maxn],s3[maxn];
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
cin>>n>>(s+);
for(int i=;i<=n;i++){
s1[i]=s1[i-]+(s[i]=='R');
s2[i]=s2[i-]+(s[i]=='P');
s3[i]=s3[i-]+(s[i]=='S');
}
int ans=;
int mx=;
for(int i=;i<=n;i++){
for(int j=i;j<=n;j++){
int x=s3[i]+(s1[j]-s1[i])+(s2[n]-s2[j]);
x-=(s2[i])+(s3[j]-s3[i])+(s1[n]-s1[j]);
if(x>){
ans++;
}
}
}
cout<<ans<<endl;
}
#ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
C 跑两遍,注意用2个数组,不要重复计算了,方法很多,可以黑暗长度大于1就直接点亮后面一个
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=1e6+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=1,ch=getchar();if(ch==EOF) return false;num=0;while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=num*10+ch-'0',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
char s[maxn];
char s2[maxn];
int ans;
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
cin>>n>>(s+1);
int ans=0;
memset(s2,'.',sizeof s2);
for(int i=1;i<=n;i++){
if(s[i]=='*') s2[i]=s2[i+1]=s2[i-1]='*';
}
for(int i=1;i<=n;i++){
if(s2[i]==s2[i+1]&&s2[i]==s2[i+2]&&s2[i]=='.'){
s2[i+1]=s2[i]=s2[i+2]='*';
ans++;
}else if(s2[i]=='.'){
s2[i+1]=s2[i]=s2[i+2]='*';
ans++;
}
}
cout<<ans<<endl;
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return 0;
}
D (补)
定义dp[i]为把i合法分割的最小花费
dp[i]可以直接转移到dp[i-1]+1
然后遍历(i-k)到i,如果出现连续,从连续处到(i-k)都可以转移到dp[i],花费为1
数据小,复杂度n^2可过
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+;
const int maxm=1e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
char s[maxn];
int dp[maxn];
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
read(n,k);
scanf("%s",s+);
memset(dp,INF,sizeof dp);
dp[]=-;
for(int i=;i<=n;i++){
dp[i]=min(dp[i],dp[i-]+);
int flag=;
for(int j=i-;j&&i-j+<=k;j--){
if(s[j]==s[j+]) flag=;
if(flag) {
dp[i]=min(dp[i],dp[j-]+);
}
}
}
cout<<dp[n]<<endl;
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
E 所有人的中,加上(100-最小值)不低于50的有多少
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime:
***********************/
#include <bits/stdc++.h>
#define show(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int maxn=1e5+;
const int maxm=1e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
int num[maxn];
bool cmp(int &a,int &b)
{
return a>b;
}
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
read(n);
for(int i=;i<n;i++){
read(num[i]);
}
sort(num,num+n,cmp);
int tmp=-num[];
int ans=;
for(int i=;i<n;i++){
if(num[i]+tmp>=) ans++;
}
printf("%d\n",ans);
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
F 给一个无向连通图,求最小瓶颈树的最大边是多少
简单推导,可知最小瓶颈树就是最小生成树,就是求最小生成树的最大边
(一开始想成了求任意两点之间的路径中的最大边...)
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=2e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
int root[maxn];
struct node{
int from,to,cost;
}e[maxm];
bool cmp(node &a,node &b){
return a.cost<b.cost;
}
int ans,t;
int find(int now){
if(now==root[now])return now;
else {
return root[now]=find(root[now]);
}
}
#define same(a,b) (find(a)==find(b))
void unite(int a,int b){
a=find(a);
b=find(b);
if(a==b)return ;
else root[a]=b;
}
void init(){
for(int i=;i<maxn;i++){
root[i]=i;
}
memset(e,,sizeof e);
}
void kruskal(){
sort(e,e+m,cmp);
for(int i=;i<m;i++){
node t=e[i];
if(!same(t.from,t.to)){
unite(t.from,t.to);
ans=max(t.cost,ans);
}
}
}
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
read(n,m);
init();
int cnt=;
for(int i=;i<m;i++){
int a,b,c;
read(a,b,c);
e[cnt++]=(node){a,b,c};
e[cnt++]=(node){b,a,c};
}
m=cnt;
ans=;
kruskal();
cout<<ans<<endl;
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
G 排个序之后直接暴力枚举所有的可能性,枚举过程中的选择用位压缩就行
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=1e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
int num[maxn];
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
read(n,m);
memset(num,0xc0,sizeof num);
for(int i=;i<n;i++){
read(num[i]);
}
sort(num,num+n);
int ans=;
for(int i=;i<<<n;i++){
int s=,mn=INF,cnt=,mx=,flag=;
for(int j=;j<n;j++){
if((i>>j)&)
s+=num[j],mx=max(num[j],mx),cnt++;
}
if(s>=m){
for(int j=;j<n;j++){
if((i>>j)&) if(s-num[j]>=m) flag=;
}
if(flag) ans=max(ans,cnt);
} }
cout<<ans<<endl;
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
H (补)
把图进行双连通分量把图缩成一颗树,在新图中用两次dfs找到树的直径,然后答案就是强连通分量的数量-直径-1
(好久没写tarjan+缩点,懵逼了)
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=1e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
struct node {int to,cost,next;}e[maxm],e2[maxm];int head[maxn],head2[maxn],nume,nume2;
void add(int a,int b,int c=,node *eg=e,int &ne=nume,int hd[]=head){eg[++ne]=(node){b,c,hd[a]};hd[a]=ne;}
int casn,n,m,k;
int low[maxn],dfn[maxn],stk[maxn];
int ins[maxn];
int top,numc,numd,belong[maxn]; void tjdfs(int now,int pre) {
dfn[now]=low[now]=++numd;
stk[++top]=now;
ins[now]=;
for(int i=head[now]; i; i=e[i].next) {
int to=e[i].to;
if(to==pre)continue;
if(ins[to]==) tjdfs(to,now);
low[now]=min(low[now],low[to]);
}
if(low[now]==dfn[now]) {
numc++;
do {
belong[stk[top]]=numc;
ins[stk[top]]=-;
} while(stk[top--]!=now);
}
}
void tjmake(){
for(int i=;i<=n;i++){
int a=belong[i];
for(int j=head[i];j;j=e[j].next){
int to=e[j].to;
int b=belong[to];
if(a==b) continue;
add(a,b,,e2,nume2,head2);
add(b,a,,e2,nume2,head2);
}
}
}
inline void tjinit(){
numc=nume2=numd=;
top=-;
memset(ins,,sizeof ins);
memset(dfn,,sizeof dfn);
memset(head2,,sizeof head);
memset(belong,,sizeof belong);
memset(low,,sizeof low);
memset(stk,,sizeof stk);
}
inline void tarjan(){
tjinit();
for(int i=;i<=n;i++) if(ins[i]==){
tjdfs(i,-);
}
tjmake();
}
int vis[maxn],cnt=,pos,ans;
void dfs(int now,int dep=){
vis[now]=;
if(dep>cnt){
cnt=dep;
pos=now;
}
for(int i=head2[now];i;i=e2[i].next){
int to=e2[i].to;
if(!vis[to]) dfs(to,dep+);
}
}
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(casn);
while(casn--){
read(n,m);
memset(head,,sizeof head);
nume=;
for(int i=;i<m;i++){
int a,b;read(a,b);
add(a,b);
add(b,a);
}
tarjan();
memset(vis,,sizeof vis);
cnt=;
pos=;
dfs();
memset(vis,,sizeof vis);
cnt=;
dfs(pos);
cout<<numc-cnt-<<endl;;
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
I (补)
暴力枚举最终到达的数字,由于只需要找到最大可行解,但是可行解不具有单调性,所以只能从n开始遍历k长
复杂度10*n^2,一开始10*n^3的算法T了,
然后用一个数组和一个变量维护改变量,复杂度可以降阶,就ac了
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e2+;
const int maxm=1e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
#define show(x) cout<<#x<<"="<<x<<endl
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m;
char s[maxn];
int add[maxn];
int t[maxn];
int main(){
#define test
#ifdef test
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
scanf("%s",s+);
int f=;
int len=strlen(s+);
for(int k=len;k>;k--){
for(int i=;i<;i++){
memset(add,,sizeof add);
for(int j=;j<=len;j++) t[j]=s[j]-'';
int tmp=;
for(int j=;j+k-<=len;j++){
tmp-=add[max(j-k,)];
int y=;
t[j]=(t[j]+tmp)%;
if(t[j]==i) continue;
if(i>t[j]) y=(i-t[j]);
else y=(i+-t[j]);
add[j]=y;
t[j]=i;
tmp+=y;
}
int flag=;
for(int j=len-k+;j<=len;j++){
tmp-=add[max(j-k,)];
if((t[j]+tmp)%!=i){
flag=;
break;
}
}
if(flag){
printf("%d\n",k);
f=;
break;
}
}
if(f) break;
}
if(f==) puts("");
} #ifdef test
fclose(stdin);
// fclose(stdout);
// system("out.txt");
#endif
return ;
}
J 桶排序记录蜡烛数量和年龄人数,遍历统计即可
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=1e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
int num[maxn],s[maxn];
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
read(n,m);
int mx=,mx2=;
memset(num,,sizeof num);
memset(s,,sizeof s);
for(int i=;i<n;i++){
int k;read(k);
s[k]++;
mx2=max(k,mx2);
} for(int i=;i<m;i++) {
int k;read(k);
num[k]++;
mx=max(k,mx);
}
int cnt=;
int ans=;
for(int i=;i<=mx2;i++){
while(cnt<=mx&&num[cnt]<s[i]) cnt++;
if(cnt>mx){
ans=;
break;
}
if(s[i]) cnt++; }
cout<<(ans?"YES":"NO")<<endl;
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
K 标记数组记录是否存在,然后遍历数组,是否k/x存在
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=1e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
int vis[maxn];
int num[maxn];
int main(){
// #define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
read(n,k);
memset(vis,,sizeof vis);
for(int i=;i<n;i++){
read(num[i]);
vis[num[i]]++;
}
sort(num,num+n);
int flag=;
for(int i=;i<n&&num[i]*num[i]<=k&&flag==;i++){
if(num[i]==) continue;
if(k%num[i]==){
if(num[i]*num[i]==k&&vis[num[i]]>=){
cout<<num[i]<<' '<<num[i]<<endl;
flag=;
}
else if(num[i]*num[i]!=k&&vis[k/num[i]]){
cout<<num[i]<<' '<<k/num[i]<<endl;
flag=;
}
}
}
if(!flag) cout<<-<<endl;
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}
L (补)
把D题的数据范围扩大了1000倍
解法依然是DP,n^2无法过 考虑n^2以下的算法
思路:
1.外层循环->无法减少
2.找到(i-k)到i之间的最早连续位置需要低于O(n)->预处理找到i之前的不连续长度达到O(1)询问
3.找到(dp[i-k]到dp[i-pos])之间的最小值,pos为最后一个连续处也需要低于O(n)->线段树维护DP数组,O(logn)查询最小值
最后在单点更新dp[i]处的答案即可
复杂度nlogn
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=1e6+;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=,ch=getchar();if(ch==EOF) return false;num=;while(ch<''||ch>''){if(ch=='-') flag=-;ch=getchar();}while(ch>=''&&ch<=''){num=num*+ch-'',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
int casn,n,m,k;
char s[maxn];
int ans;
int lst[maxn<<];
int num[maxn];
#define mid ((l+r)>>1)
int rmin(int s,int t,int l=,int r=n,int now=){
if(l>r||t<l||s>r) return INF;
if(s<=l&&t>=r) return lst[now];
return min(rmin(s,t,l,mid,now<<),rmin(s,t,mid+,r,now<<|));
}
void upd(int pos,int x,int l=,int r=n,int now=){
if(l>r||pos<l||pos>r) return;
lst[now]=min(x,lst[now]);
if(l==r) return;
upd(pos,x,l,mid,now<<);
upd(pos,x,mid+,r,now<<|);
}
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif read(casn);
while(casn--){
read(n,k);
scanf("%s",s+);
ans=;
memset(lst,INF,sizeof lst);
memset(num,,sizeof num);
#define show(x) cout<<#x<<"="<<x<<endl
for(int i=;i<=n;i++){
if(s[i]!=s[i-]) num[i]=num[i-]+;
else num[i]=;
}
upd(,);
for(int i=;i<=n;i++){
ans++;
if(i-num[i]>=max(i-k,)+)
ans=min(ans,rmin(max(i-k,),i-num[i]-)+);
upd(i,ans);
}
cout<<ans-<<endl;
} #ifdef test
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return ;
}