题很好，只不过咱不会做。
T1
模拟即可。
#include<cstdio>
//#define zczc
const int N=600010;
inline void read(int &wh){
wh=0;int f=1;char w=getchar();
while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); }
wh*=f;return;
}
inline bool get(){
char w=getchar();
while(w!='0'&&w!='1')w=getchar();
return w=='1';
}
inline void check(int &s1,int s2){if(s1<s2)s1=s2;return;}
int m,ans,l[N],r[N];
bool a[N];
signed main(){
#ifdef zczc
freopen("in.txt","r",stdin);
#endif
#ifndef zczc
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
read(m);
for(int i=1;i<=m;i++)a[i]=get();
for(int i=1;i<=m;i++)l[i]=a[i]==a[i-1]?l[i-1]:i-1;
for(int i=m;i;i--)r[i]=(a[i]==a[i+1]&&i!=m)?r[i+1]:i+1;
for(int i=1;i<=m;i++)check(ans,r[r[i]]-l[l[i]]-r[i]+l[i]),check(ans,r[i]-l[i]-1);
printf("%d",ans);
return 0;
}
T2
- 解法
可以想到用 \(f[i][j]\) 表示以 \(a_i\) 和 \(a_j\) 结尾的合法序列的最大长度，然后更新即可。主要问题是在后面那么多数中找到一个恰好等于 \(a_i+a_j\) 的数，哈希即可，虽然我卡了半天常又吸了半天氧才过，后来看题解发现似乎对于每个数只需要更新它后面第一个符合条件的数即可，因为这样肯定可以保证最优……
太弱了。
#include<cstdio>
#include<vector>
#define abs(wh) (wh<0?wh+inf:wh)
//#define zczc
using namespace std;
const int N=3010;
const int M=100011;
const int inf=1e9+7;
inline void read(int &wh){
wh=0;int f=1;char w=getchar();
while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); }
wh*=f;return;
}
inline void check(int &s1,int s2){
if(s1<s2)s1=s2;return;
}
int num[N],cnt;
struct node{
int val,pl,next,beg;
}h[M];
int hsum,head[M];
inline void push(node wh){
int pl=abs(wh.val)%M;
hsum++;
h[hsum]=wh;
h[hsum].next=head[pl];
h[head[pl]].beg=hsum;
head[pl]=hsum;
return;
}
void find(int wh,int val){
int pl=abs(val)%M;cnt=0;
for(int i=head[pl];i;i=h[i].next){
if(h[i].val==val){
if(h[i].pl>wh)num[++cnt]=h[i].pl;
else h[h[i].beg].next=h[i].next;
}
}
return;
}
int m,a[N],f[N][N],ans;
signed main(){
#ifdef zczc
freopen("in.txt","r",stdin);
#endif
#ifndef zczc
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
read(m);
for(int i=1;i<=m;i++){
read(a[i]);
push((node){a[i],i,0});
}
for(int i=2;i<=m;i++){
for(int j=1;j<i;j++){
check(f[i][j],2);
check(ans,f[i][j]);
find(i,a[i]+a[j]);
for(int k=1;k<=cnt;k++)check(f[num[k]][i],f[i][j]+1);
}
}
printf("%d",ans);
return 0;
}
T3
还没写出来。略过。
T4
很有趣的一道卡常题，专门讲一下。