网站分析总结qq推广
ABC322刷题记
T1.A
A - First ABC 2。
妥妥的简单题……
用find函数做就行。（如果不存在那个子串就返回-1，否则返回第一次出现位置）
注意题目中编号是从1开始的。
时间复杂度：O(log(n))。find函数有一定代价，我记得是log。
#include<bits/stdc++.h>
using namespace std;
string str="";
int n=0;
int main(){
scanf("%d",&n);
cin>>str;
//输入
str=" "+str;
//处理：把0开头改成1开头
printf("%d\n",str.find("ABC"));
//输出答案
return 0;
}
T2.B
B - Prefix and Suffix。
前两题都一样简单。
用substr截取出t中与s长度相同的前缀和后缀，分别和s比较即可。
时间复杂度先不算了，因为肯定够。
#include<bits/stdc++.h>
using namespace std;
int m=0,n=0;
string s="",t="";
int main(){
scanf("%d%d",&n,&m);
cin>>s>>t;
//输入
string front=t.substr(0,n),rear=t.substr(m-n,n);
//去除前缀与后缀
if(front==s&&rear==s){
printf("0\n");
}else{
if(front==s&&rear!=s){
printf("1\n");
}else{
if(front!=s&&rear==s){
printf("2\n");
}else{
printf("3\n");
}
}
}
//对号入座，输出不错
return 0;
}
T3.C
C - Festival。
还是辣墨简单……
用b数组记录某一天是否有烟花，在用ans数组从后往前算，其中ans[i]表示离第i天最近并且时间不比第i天早的放烟花的日子与第i天相差多少。
最后从1到n输出ans的对应项即可。
时间复杂度：O(n)，应该是最优的思路了。
#include<bits/stdc++.h>
#define M 220000
#define N 220000
using namespace std;
int ans[N]={},a[M]={},m=0,n=0;
bool b[N]={};
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);
b[a[i]]=true;
}
//输入，并维护b数组
for(int i=n;i>=1;i--){
if(b[i]==true){
ans[i]=0;
//①当前这一天就有烟花：距离为0
}else{
ans[i]=ans[i+1]+1;
//②当前这一天没有烟花：比明天的距离多一天
}
}
//计算ans
for(int i=1;i<=n;i++){
printf("%d\n",ans[i]);
}
//输出答案
return 0;
}
T4.D
D - Polyomino。
客观来说，我这道题没做出来真有些丢人。
其实就是一个dfs，但是一个变量名害我找了1天6小时34分钟……
我们定义一个结构体，存储一块牌，如果一个坐标上有点，就记录为1，否则记录为0。支持项各个方向平移（如果会出格，就返回不能做，否则返回操作成功）、顺时针旋转、逆时针旋转操作，当然还要封装加法（把骨牌拼接起来，其实就是相同坐标的点记录的数相加，如果相加后和为0，就说明这里本来就没有点，如果为1就说明刚好有一个牌上有，如果大于1就说明有多个牌子上面有这个点，当然，只有当3块牌都记起来之后和为1才能说明这种摆法可能合法）、等于号（骨牌完全相同，用于判断拼完之后是不是和满牌相同）。
在dfs中，我们不难证明先旋转（遍历旋转次数，去时顺时针，回时逆时针），在平移（反方向的平移互相作为返回操作）是不会有问题的，当然要注意平移可以项各种方向平移多次。
最终大体流程是这样：使用dfs，遍历三个牌的操作，如果最后拼起来是满牌就说明可以达成目的，直接标记最终答案为“可行”，并一路退出回到主程序，否则继续往下遍历。遍历操做时，先考虑旋转，再考虑平移。最后输出Yes/No即可。
时间复杂度不好算，这里不展开描述，但是数据量都是4、16这类数，估计也没啥事。
#include<bits/stdc++.h>
using namespace std;
struct Info{
int num[4][4];
Info operator+(Info ot){
Info ret={};
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
ret.num[i][j]=num[i][j]+ot.num[i][j];
}
}
return ret;
}
//拼接
bool operator==(Info ot){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(num[i][j]!=ot.num[i][j]){
return false;
}
}
}
return true;
}
//判等
bool down(){
for(int i=0;i<4;i++){
if(num[3][i]==1){
return false;
}
}
for(int i=3;i>=1;i--){
for(int j=0;j<4;j++){
num[i][j]=num[i-1][j];
}
}
for(int i=0;i<4;i++){
num[0][i]=0;
}
return true;
}
//下移
bool left(){
for(int i=0;i<4;i++){
if(num[i][0]==1){
return false;
}
}
for(int i=0;i<=2;i++){
for(int j=0;j<4;j++){
num[j][i]=num[j][i+1];
}
}
for(int i=0;i<4;i++){
num[i][3]=0;
}
return true;
}
//左移
bool right(){
for(int i=0;i<4;i++){
if(num[i][3]==1){
return false;
}
}
for(int i=3;i>=1;i--){
for(int j=0;j<4;j++){
num[j][i]=num[j][i-1];
}
}
for(int i=0;i<4;i++){
num[i][0]=0;
}
return true;
}
//右移
bool up(){
for(int i=0;i<4;i++){
if(num[0][i]==1){
return false;
}
}
for(int i=0;i<=2;i++){
for(int j=0;j<4;j++){
num[i][j]=num[i+1][j];
}
}
for(int i=0;i<4;i++){
num[3][i]=0;
}
return true;
}
//上移
void spina(){
Info ret={};
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
ret.num[i][j]=num[3-j][i];
}
}
memcpy(num,ret.num,sizeof(num));
return;
}
//顺时针旋转
void spinb(){
Info ret={};
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
ret.num[i][j]=num[j][3-i];
}
}
memcpy(num,ret.num,sizeof(num));
return;
}
//逆时针旋转
};
Info inf[10]={};
bool ans=false;
inline void dfs(int d);
//深度优先搜索用到函数
inline void tmovew(int d);
//遍历旋转，用完后返回原始状态
inline void tmovex(int d);
//遍历横移，用完后返回原始状态
inline void tmovey(int d);
//遍历竖移，用完后返回原始状态
int main(){
inf[4]={{{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}}};
//满牌
for(int i=0;i<4;i++){
string str="";
cin>>str;
for(int j=0;j<4;j++){
if(str[j]=='#'){
inf[1].num[i][j]=1;
}
}
}
for(int i=0;i<4;i++){
string str="";
cin>>str;
for(int j=0;j<4;j++){
if(str[j]=='#'){
inf[2].num[i][j]=1;
}
}
}
for(int i=0;i<4;i++){
string str="";
cin>>str;
for(int j=0;j<4;j++){
if(str[j]=='#'){
inf[3].num[i][j]=1;
}
}
}
//输入，并处理成Info格式
dfs(1);
//dfs
if(ans==false){
printf("No\n");
}else{
printf("Yes\n");
}
//根据答案输出
return 0;
}
inline void dfs(int d){
if(d==4){
//3个骨牌遍历完成
if(inf[1]+inf[2]+inf[3]==inf[4]){
ans=true;
//若相加为满牌，就说明答案可行，直接记录答案为“Yes”，或者说true
}
return;
//递归出口
}
if(ans==true){
return;
//已经找到答案，无需继续遍历
}
tmovew(d);
//开始遍历旋转
return;
}
inline void tmovew(int d){
for(int i=0;i<=3;i++){
for(int j=1;j<=i;j++){
inf[d].spina();
}
//顺时针旋转相应次
tmovex(d);
//往下遍历横移
for(int j=1;j<=i;j++){
inf[d].spinb();
}
//逆时针转回去（回溯）
}
return;
}
inline void tmovex(int d){
for(int i=0;i<=4;i++){
int sum=0;
//尽最大可能地往相应方向移动i次，sum记录实际上操作成功的次数，后面所有的sum都同理
for(int j=1;j<=i;j++){
if(inf[d].left()==true){
sum++;
}
}
//往左移动
tmovey(d);
//往下遍历竖移
for(int j=1;j<=sum;j++){
inf[d].right();
}
//往右移动，也就是回溯
}
for(int i=0;i<=4;i++){
int sum=0;
for(int j=1;j<=i;j++){
if(inf[d].right()==true){
sum++;
}
}
//往右移动
tmovey(d);
//往下遍历竖移
for(int j=1;j<=sum;j++){
inf[d].left();
}
//往左移动，也就是回溯
}
return;
}
inline void tmovey(int d){
for(int i=0;i<=4;i++){
int sum=0;
for(int j=1;j<=i;j++){
if(inf[d].down()==true){
sum++;
}
}
//往下移动
dfs(d+1);
//往下递归
for(int j=1;j<=sum;j++){
inf[d].up();
}
//往上移动，也就是回溯
}
for(int i=0;i<=4;i++){
int sum=0;
for(int j=1;j<=i;j++){
if(inf[d].up()==true){
sum++;
}
}
//往上移动
dfs(d+1);
//往下递归
for(int j=1;j<=sum;j++){
inf[d].down();
}
//往下移动，也就是回溯
}
return;
}