头像

2010

$\href{https://www.acwing.com/file_system/file/content/whole/index/content/4476149/}{{个人主页}}$封禁家族的蒟蒻




离线:1天前


最近来访(3901)
用户头像
Royal
用户头像
SmiLeeeee
用户头像
我不明智
用户头像
花开忘忧
用户头像
TTL
用户头像
落月成孤倚灬
用户头像
NOI_AK_dreeeam
用户头像
爱宣纸
用户头像
梦若浮生
用户头像
L_B_L
用户头像
AcWing2010
用户头像
垫底抽風
用户头像
ash_heat
用户头像
Carl
用户头像
Destiny688
用户头像
迎风飘扬
用户头像
打小就酷
用户头像
ljh_lxy
用户头像
雪落之声-2010
用户头像
DreamFather


2010
9天前

求调代码,样例过不了

#include<bits/stdc++.h>
using namespace std;
int const N=1000100;
int b,e,len,v,x1[N],x2[N],k,cnt;
char way;
int main() {
    scanf("%d%d",&b,&e);
    while(b--) {
        cin>>len>>way;
        way=='l'?v=-1:v=1;//根据方向求出速度
        while(len--) {//存储走的每一步
            k++;
            x1[k]=x1[k-1]+v;
        }
    }
    while(++k<N) x1[k]=x1[k-1];
    k=0;
    while(e--) {
        cin>>len>>way;
        way=='l'?v=-1:v=1;//根据方向求出速度
        while(len--) {//存储走的每一步
            k++;
            x2[k]=x2[k-1]+v;
        }
    }
    while(++k<N) x2[k]=x2[k-1];
    for(int i=1; i<N; i++) {//统计相遇次数
        //如果在时间点i两头牛都在同一点而且上一个时间点不在同一个点,则为相遇
        if(x1[i]==x2[i]&&x1[i-1]!=x2[i-1]) cnt++;
    }
    printf("%d",cnt);
    return 0;
}



2010
11天前

1344. 转换

$USACO$ 题目

题目传送门

看了一下,自己的方法跟y总的不一样,而且似乎题解里面没有和我一样的做法,所以就跑来写题解了~(虽然有一两个和我的做法有点像,但是我在 $AC$ 之前真的没有看过题解哦~大家就资瓷一下吧~)


算法:找规律、二维数组下标技巧

除了直接翻转图案,还有什么更好的方法呢?

通过分析,我们还可以发现这题其实可以不用直接翻转图案,而是利用二维数组翻转后下标的规律。

首先,我们可以先开一个bool数组,用来表示前$6$种的转换方式是否可行。

如果前$6$种方法都不可行,就直接输出$7$。

那么,如何判断每种转换方式是否可行呢?

我们可以遍历二维数组$b$(新图案)中的每一个字符,判断这个字符转换后的位置是否与二维数组$a$当前位置的字符相同,若不相同直接将该转换方式标记为true(不可行)

下面是前$6$种转换方式的规律:

1. $90$ 度旋转:将图案顺时针旋转 $90$ 度。

通过找规律发现,i,j旋转 $90$ 度后下标变为j,n-i+1

所以a[i][j]->a[j][n-i+1]

2. $180$ 度旋转:将图案顺时针旋转 $180$ 度。

旋转 $180$ 度就相当于旋转2次 $90$ 度,第1次旋转为j,n-i+1,那么第2次旋转就是n-i+1,n-j+1

所以a[i][j]->a[n-i+1][n-j+1]

3. $270$ 度旋转:将图案顺时针旋转 $270$ 度。

同理,旋转 $270$ 度相当于旋转3次 $90$ 度,那么第3次旋转就是n-j+1,n-(n-j+1)+1

所以a[i][j]->a[n-j+1][n-(n-j+1)+1

4.镜像:沿着图片的中间垂直线翻转图片,使其变为自身的镜像。

这里需要注意的是,题目指的是左右翻转,而不是上下翻转

由于是左右翻转,i肯定是不会变的,因为左右翻转后肯定还是在那一行,只是改变了列。j改变的规律也很好找,规律就是原来该元素是在左数第几个位置,那么翻转后它的位置就是在右数第几个位置,从而得出j变为n-j+1

所以a[i][j]->a[i][n-j+1]

5.组合:先进行镜像转换,再按照1∼3中的一种方式进行转换。

这种操作比较麻烦,因为镜像转换后还有有3种可能:操作1,操作2,操作3

那么我们可以分情况讨论,先开设一个新的bool数组,分别表示操作1,操作2,操作3是否可行。到最后再判断一下,如果三种可能都不可行,就代表操作5不可行

我们先把操作4的规律写下来,再按照前面1~3操作的方式得出规律

所以3种可能的规律分别是a[i][j]->a[n-j+1][n-i+1],a[i][j]->a[n-i+1][n-(n-j+1)+1],a[i][j]->a[n-(n-j+1)+1][n-(n-i+1)+1]

6.不改变:保持原图案,不做任何改变。

这种操作就非常简单了,位置不作任何改变

所以,a[i][j]->a[i][j]

最后,把所有的规律整合起来,就可以写出代码了


c++代码

#include<bits/stdc++.h>
using namespace std;
int n;
char a[20][20],b[20][20];
bool r[17],r5[13];
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) cin>>a[i][j];
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) cin>>b[i][j];
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(b[j][n-i+1]!=a[i][j]) r[1]=true;
            if(b[n-i+1][n-j+1]!=a[i][j]) r[2]=true;
            if(b[n-j+1][n-(n-i+1)+1]!=a[i][j]) r[3]=true;
            if(b[i][n-j+1]!=a[i][j]) r[4]=true;
            if(b[n-j+1][n-i+1]!=a[i][j]) r5[1]=true;
            if(b[n-i+1][n-(n-j+1)+1]!=a[i][j]) r5[2]=true;
            if(b[n-(n-j+1)+1][n-(n-i+1)+1]!=a[i][j]) r5[3]=true;
            if(b[i][j]!=a[i][j]) r[6]=true;
        }
    }
    if(r5[1]&&r5[2]&&r5[3]) r[5]=true;
    for(int i=1; i<=6; i++) {
        if(!r[i]) {
            printf("%d",i);
            return 0;
        }
    }
    printf("7");
    return 0;
}

制作不易!!!禁止抄袭!!!




2010
12天前

洛谷 P6523 「Wdoi-1」加密通信

题目传送门


贪心(20分做法)

因为题目要求 $B_i \times B_{i+1}=A_i$ ,而且 $B_i$ 和 $B_{i+1}$ 都得是质数,所以 $A_i$ 必须符合以下条件:

  1. $A_i$ 只有两个质因数

  2. $A_i$ 的质因数必须在 $[1,M]$ 范围内

  3. $A_i$ 和 $A_{i-1}$ 有共同的质因数

于是我们可以考虑分解质因数来进行判断和构造出密文 $B$

因为这个思路只能拿20分,所以我不再赘述,具体操作过程请看代码和代码注释

20pts代码:

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[100100],x1,x2,a2,b[100100];
bool r,f;
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        f=true;
        for(int i=1; i<n; i++) {
            scanf("%d",&a[i]);
            if(!f) continue;//已经输出过-1就不用管了
            x1=0,x2=0,r=true;//只有两个质因数的才符合条件,所以开两个变量存就够了
            a2=a[i];
            for(int j=2; j*j<=a2&&j<=m; j++) {//分解质因数
                while(a2%j==0) {
                    if(!x1) x1=j;//两个都没存过
                    else if(x1&&!x2) x2=j;//x1存过了,x2没存过
                    else if(x1&&x2) {//都存过了,而且超过了两个质因数,不符合条件
                        r=false;
                        break;
                    }
                    a2/=j;
                }
            }
            if(a2>m) r=false;
            if(a2>1) {//还没分解完
                if(!x1) x1=a2;
                else if(x1&&!x2) x2=a2;
                else if(x1&&x2) r=false;
            }
            if(r&&x1&&x2) {//符合条件
                if(i==1) {//如果是第一个数就得存两个
                    b[1]=x1;
                    b[2]=x2;
                } else if(x1==b[i]) b[i+1]=x2;
                else if(x2==b[i]) b[i+2]=x1;
                else {//当前数的两个质因数和前一个数没有相同的,输出-1
                    printf("-1\n");
                    f=false;
                }
            } else {
                printf("-1\n");
                f=false;
            }
        }
        if(f) {//如果存在符合条件的,就输出
            for(int i=1; i<=n; i++) printf("%d ",b[i]);
            printf("\n");
        }
    }
    return 0;
}

递推(100分做法)

由于 $B$ 是递推形式,只要知道一个 $B_i$ ,那么就可以得知整个数列。考虑到 $B_{i-1} \times B_i=A_{i-1}$ , $B_i \times B_{i+1}=A_i$
,可得知 $B$ 的所有数。令 $B_{num}=gcd(A_{num-1},A_{num})$ ,即可往两边递推得到答案。记得判断 $B_i$ 是否在 $[1,M]$ 范围内。

详细操作过程见代码和代码注释

100pts代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//不开long long见祖宗
ll n,m,t,a[100100],b[100100],num;
bool r;
ll gcd1(ll a1,ll b1) {//辗转相除法求最大公约数
    return b1==0?a1:gcd1(b1,a1%b1);
}
int main() {
    scanf("%lld",&t);
    while(t--) {
        scanf("%lld%lld",&n,&m);
        for(int i=1; i<n; i++) scanf("%lld",&a[i]);
        num=0;
        for(int i=1; i<n-1; i++) {
            if(a[i]!=a[i+1]) {//若两数不同,则求最大公约数
                b[i+1]=gcd1(a[i],a[i+1]);
                num=i;//标记下标
                break;
            }
        }
        r=true;
        for(int i=num; i>=1; i--) {//算出num左边的
            if(b[i+1]) b[i]=a[i]/b[i+1];
        }
        for(int i=num+1; i<=n; i++) {//算出num右边的
            if(b[i-1]) b[i]=a[i-1]/b[i-1];
        }
        for(int i=1; i<=n; i++) {//判断b[i]是否在[1,m]区间内
            if(b[i]>m||b[i]<1) {
                r=false;
                break;
            }
        }
        //输出
        if(r) {
            for(int i=1; i<=n; i++) printf("%lld ",b[i]);
            printf("\n");
        } else printf("-1\n");
    }
    return 0;
}

温馨提示:十年oi一场空,不开long long见祖宗!


彩蛋

《关于洛谷提交题解有多严格这件事》

第一次提交:

1.PNG

经过精心修改后第二次提交:

2.PNG

连乘号都这么讲究吗。。。


制作不易!!!禁止抄袭!!!



活动打卡代码 AcWing 2003. 找到牛!

2010
27天前

遍历整个字符串,遇到一对左括号加到l里面,不加到cnt里面是因为个数取决于右括号而不是左括号(就像如果一个字符串的所有字符都是左括号,没有右括号,也无法匹配)

遇到一对右括号就把l加到cnt里面,因为这对右括号可以跟前面的所有左括号匹配,而l存储的刚好是它前面左括号的对数

#include<bits/stdc++.h>
using namespace std;
string s;
int l,cnt;
int main() {
    cin>>s;
    for(int i=0; i<s.size()-1; i++) {//这里写i<s.size()-1是因为括号必须是((或者)),轮到最后一个就不可能跟下一个字符组成一对(因为下一个字符是空)
        if(s[i]=='('&&s[i+1]=='(') l++;//左边的一对括号++
        if(s[i]==')'&&s[i+1]==')') cnt+=l;//组成一对右括号,这对右括号可以跟前面所有的左括号匹配
    }
    printf("%d",cnt);
    return 0;
}


活动打卡代码 AcWing 426. 开心的金明

2010
1个月前

没啥好说的,01背包模板,不太一样的是要把每件物品的重要程度乘上重量

01背包的详细做法见这里

#include<bits/stdc++.h>
using namespace std;
int n,m,v,p,dp[30100];
int main() {
    scanf("%d%d",&m,&n);
    for(int i=1; i<=n; i++) {
        scanf("%d%d",&v,&p);
        p*=v;
        for(int j=m; j>=v; j--) dp[j]=max(dp[j],dp[j-v]+p);
    }
    printf("%d",dp[m]);
    return 0;
}


活动打卡代码 AcWing 756. 蛇形矩阵

2010
2个月前

这题可以用搜索解决

解释一下为什么搜索不写递归而是写循环:

如果不知道要搜索几次,就用递归(因为$4$个方向去搜,你能提前不知道过程会遇到什么障碍)

如果像这题,已经明确搜索的路径(就是一圈一圈地走),知道要填的数一共有n*m个,就可以用循环

搜索的技巧:$1$代表右,$2$代表下,$3$代表左,$4$代表上。每次判断下一步会不会出边界,如果会,方向$+1$,如果方向变量$>4$,%$4$就可以了

#include<bits/stdc++.h>
using namespace std;
int n,m,x=1,y=1,dx[14]= {0,0,1,0,-1},dy[14]= {0,1,0,-1,0},d=1,a[110][110];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n*m; i++) {
        a[x][y]=i;
        //移动一格
        x+=dx[d];
        y+=dy[d];
        if(x<=0||x>n||y<=0||y>m||a[x][y]) {//顺时针转90度
            x-=dx[d];
            y-=dy[d];
            d++;//改变方向
            if(d>4) d%=4;
            x+=dx[d];
            y+=dy[d];
        }
    }
    for(int i=1; i<=n; i++) {//输出矩阵
        for(int j=1; j<=m; j++) printf("%d ",a[i][j]);
        printf("\n");
    }
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

2010
2个月前

很经典的洪水灌溉问题(今年csp-j初赛完善程序2也考了hh)

读入的时候先把@(深搜的出发点)坐标存下来

每次搜索计数器都$+1$,搜过的点要标记一下,防止重复算

然后向四个方向搜索,如果是黑色的而且没有走过、没有出界的话就搜索

记得每次把计数器cnt清空

#include<bits/stdc++.h>
using namespace std;
int w,h,sx,sy,cnt,tx,ty,dx[14]= {0,0,1,0,-1},dy[14]= {0,1,0,-1,0};
char a[30][30];
void dfs(int x,int y) {//深搜
    cnt++;
    a[x][y]='#';//标记(防止重复算)
    for(int i=1; i<=4; i++) {//向4方向搜索
        tx=x+dx[i];
        ty=y+dy[i];
        if(a[tx][ty]=='.'&&tx>=1&&tx<=h&&ty>=1&&ty<=w) dfs(tx,ty);//符合条件就搜索
    }
}
int main() {
    while(true) {
        scanf("%d%d",&w,&h);
        if(!w&&!h) return 0;
        cnt=0;//计数器清空
        for(int i=1; i<=h; i++) {
            for(int j=1; j<=w; j++) {
                cin>>a[i][j];
                {
                    if(a[i][j]=='@') {//标记出发点
                        sx=i;
                        sy=j;
                    }
                }
            }
        }
        dfs(sx,sy);
        printf("%d\n",cnt);
    }
    return 0;
}


活动打卡代码 AcWing 433. ISBN号码

2010
2个月前

先用字符串形式输入$ISBN$号码,把$9$位数字分别乘$1,2,…,9$再用$sum$求和

求出识别码后,如果正确就输出Right,否则输出是正确的$ISBN$号码

#include<bits/stdc++.h>
using namespace std;
string a;//a:ISBN号码
int c=1,sum=0,x;//c:9位数字乘的数 x:正确的识别码
int main() {
    cin>>a;
    for(int i=0; i<a.size()-1; i++) {
        //9位数字分别乘1,2,...,9再用sum求和
        if(a[i]!='-') {
            sum=sum+(a[i]-48)*c;
            c++;
        }
    }
    x=sum%11;//求出识别码
    //假如识别码正确,那么输出Right
    if(x==a[a.size()-1]-48||x==10&&a[a.size()-1]=='X') {
        printf("Right");
        return 0;
    }
    //如果余数为10,则识别码为X
    if(x==10) a[a.size()-1]='X';
    else a[a.size()-1]=x+48;
    cout<<a;
    return 0;
}


活动打卡代码 AcWing 419. FBI树

2010
2个月前

一道二叉树$water$题,用搜索、构造、二分即可(这里的二分意思其实就是分成两半hh)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k=2;
string s;
struct node {
    ll lc,rc;
    string num;
} a[100100];
string fun(ll c,string x) {//二分
    string x1="";
    if(c==1) {
        for(ll i=0; i<x.size()/2; i++) x1+=x[i];
    } else {
        for(ll i=x.size()/2; i<x.size(); i++) x1+=x[i];
    }
    return x1;
}
char ch(string s1) {//构造
    ll sum0=0,sum1=0;
    for(ll i=0; i<s1.size(); i++) {
        if(s1[i]=='0') sum0++;
        else sum1++;
    }
    if(sum1==0&&sum0==s1.size()) return 'B';
    if(sum0==0&&sum1==s1.size()) return 'I';
    return 'F';
}
void dfs(ll x) {//搜索
    if(a[x].lc) dfs(a[x].lc);
    if(a[x].rc) dfs(a[x].rc);
    cout<<ch(a[x].num);
}
int main() {
    scanf("%lld",&n);
    cin>>s;
    a[1].num=s;
    n=(ll)pow(2,n);
    for(ll i=1; i<=n*2+1; i++) {
        if(a[i].num.size()==1) continue;
        a[k++].num=fun(1,a[i].num);
        a[k++].num=fun(2,a[i].num);
        a[i].lc=k-2;
        a[i].rc=k-1;
    }
    dfs(1);
    return 0;
}


活动打卡代码 AcWing 415. 栈

2010
2个月前

初始值:dp[0]=1;dp[1]=1;

设$x$为当前出栈序列的最后一个,则$x$有$n$种取值

由于$x$是最后一个出栈的,所以可以将已经出栈的数分成两部分:比$x$小和比$x$大

经过推导可以得出动态转移方程:dp[i]+=dp[j]*dp[i-j-1]

/*
动态转移方程:dp[i]+=dp[j]*dp[i-j-1]
*/
#include<bits/stdc++.h>
using namespace std;
int n,dp[28]= {1,1};
int main() {
    scanf("%d",&n);
    for(int i=2; i<=n; i++) {
        for(int j=0; j<i; j++) dp[i]+=dp[j]*dp[i-j-1];
    }
    printf("%d",dp[n]);
    return 0;
}