Preface
这次难度感觉挺平均的，前面的题不水，后面的题也不毒瘤（可能是因为我做的不够后面）
A. Special Characters
开局构造题。
因为特殊字符一定是成对出现的（包括两边的，可以分类讨论思考一下），所以只有 \(n\) 为偶数的时候才有解。
然后直接以 AABBAABB... 的格式输够 \(n\) 个就行了。
点击查看代码
#include<cstdio>
using namespace std;
int main()
{
int T; scanf("%d",&T);
while(T--)
{
int n; scanf("%d",&n);
if(n&1) printf("NO\n");
else
{
printf("YES\n");
for(int i=1;i<=n>>1;i++)
{
char ch='A'+(i&1);
putchar(ch),putchar(ch);
}
putchar('\n');
}
}
return 0;
}
B. Array Fix
利用贪心，让前面的数拆的尽量小，所以只要可以拆（十位大于个位且拆开后比前面打）就直接拆，最后判断是不是不降序列。
点击查看代码
#include<cstdio>
using namespace std;
const int N=55;
int n,a[N];
int m,b[N<<1];
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
m=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]<10) b[++m]=a[i];
else
{
if(a[i]/10>=b[m] && a[i]/10<=a[i]%10)
{
b[++m]=a[i]/10;
b[++m]=a[i]%10;
}
else b[++m]=a[i];
}
}
bool ans=true;
for(int i=2;i<=m;i++)
if(b[i]<b[i-1])
{
ans=false;
break;
}
printf("%s\n",ans?"YES":"NO");
}
return 0;
}
C. Arrow Path
类似图遍历的处理方法，记录每一个位置能否通过第一/二步到达，然后转换步骤尝试再走。
最后判断终点是否能以第二步到达。
点击查看代码
#include<cstdio>
#include<queue>
using namespace std;
const int N=2e5+5;
int n;
char str[5][N];
bool arrow[5][N];
bool f[5][N],g[5][N]; //can reach there by step 1/2
const int dx[5]={1,-1,0,0};
const int dy[5]={0,0,1,-1};
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%s%s",&n,str[1]+1,str[2]+1);
for(int i=1;i<=n;i++)
{
f[1][i]=f[2][i]=g[1][i]=g[2][i]=false;
arrow[1][i]=str[1][i]=='>';
arrow[2][i]=str[2][i]=='>';
//0-'<'; 1-'>'
}
queue<pair<pair<int,int>,bool>> q;
q.push({{1,1},0});
while(!q.empty())
{
int x=q.front().first.first,y=q.front().first.second;
bool type=q.front().second;
q.pop();
if(type==0) //to go step1
{
for(int i=0;i<4;i++)
{
int tx=x+dx[i],ty=y+dy[i];
if(tx>=1&&tx<=2 && ty>=1&&ty<=n && !f[tx][ty])
{
f[tx][ty]=true;
q.push({{tx,ty},1});
}
}
}
if(type==1) //to go step2
{
int tx=x,ty=y;
if(arrow[x][y]) ty++;
else ty--;
if(tx>=1&&tx<=2 && ty>=1&&ty<=n && !g[tx][ty])
{
g[tx][ty]=true;
q.push({{tx,ty},0});
}
}
}
printf("%s\n",g[2][n]?"YES":"NO");
}
return 0;
}
D. Tandem Repeats?
如果我告诉你我是用暴力 \(O(N^3)\) 卡过的你信吗？
就是枚举两段序列开头，然后暴力判断是否合法。
然后剪枝 + 各种反转搜索顺序 + 猜测 Hack 数据就稀里糊涂卡过了（\(1609\) ms）
不建议学，可以去看下正解。
点击查看代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5005;
int n; char s[N];
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%s",s+1);
n=strlen(s+1);
int ans=0;
for(int l1=1;l1<=n&&l1<=n-(ans<<1);l1++)
{
// if(ans>=(n-l1+1)>>1) break;
for(int l2=l1+((n-l1+1)>>1);l2>l1&&l2>ans+l1;l2--)
{
// if(ans>=l2-l1) break;
bool flag=true;
for(int len=l2-l1;len>=1;len--)
{
int p1=l1+len-1,p2=l2+len-1;
if(!(s[p1]=='?'||s[p2]=='?' || s[p1]==s[p2]))
{flag=false; break;}
}
if(flag) ans=max(ans,l2-l1);
}
}
printf("%d\n",ans<<1);
}
return 0;
}
E. Clique Partition
正在施工……
标签：Educational,Rated,int,scanf,Codeforces,l2,&&,l1,include From： https://www.cnblogs.com/jerrycyx/p/18512693