头像

凌风_5




离线:2个月前


最近来访(0)


凌风_5
3个月前

题意就是在方格中走到指定点的方案数,

样例

数据范围
1≤n,m≤30
输入样例1:
3 4
输出样例1:
2
输入样例2:
6 6
输出样例2:
0

算法1

组合数学O(n+m)

主要题意处理:

当行列同时为偶数时此方格不能经过,意思就是每次走两格,目的地不能达到的方案数为0;

公式为:C(min(n/2-1,m/2-1),n+m-2-n/2-m/2)

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main (){
    int n,m;
    cin >> n >> m;
    if(!(n%2 || m%2)){
        cout << 0<<endl;
        return 0;
    }
    n = n - n/2 - 1;
    m = m - m/2 - 1;
    long long t1 = 1;
    long long t2 = 1;
    for(int i = 0; i < min (n,m); i++){
        t1 *= (n+m-i);
    }
    for(int i = 1; i <= min(n,m); i++){
        t2 *= i;
    }
    cout << t1/t2<<endl;
    return 0;
}



凌风_5
4个月前

可以模拟理解一下代码
主要是理解数组a的作用

#include <bits/stdc++.h>
using namespace std;

int n,m;
int pd (int i){
    int t = i % n;
    for(int j = 0;t <= i;t += n){
        if(t % m == 0) {return 0;}
    }
    return 1;
}

int main(){
    int a[10001];//a数组作用:确定1-n范围是否可以被达到
    memset (a,0,sizeof(a));
    cin >> n >> m;
    int t,k;
    if(n < m ) { t = m;m = n;n = t;}//n为 max,m 为 min
    int i = 0,j = n;
    a[0] = 1;t = 1;k = n-1;
    while(i < j){ a[i] = 1; i += m ;}
    for(;;i+=m){
        if(i > j + n) j += n;
        a[i - j] = 1;
        for(; k >=1;k--){
            if(!a[k]){t = j + k;break;};
        }
        if(k == 0)break;
    }
    int t1 = 1;
    for(int i = t; i > 1; i--){
        if(pd(i) && t1 < i){
            t1 = i;
            break;
        }
    }
    cout << t1<<endl;
    return 0;
}


活动打卡代码 AcWing 3257. 跳一跳

凌风_5
4个月前
#include <bits/stdc++.h>
using namespace std;

int main(){
    int ans = 0,t1,t2 = 0,t3 = 0;
    bool isf = true;
    // cin >> t1;
    // if(t1 == 2) ans += 2;
    while(cin >> t1){
        if(t1) {
            if(t1 == 1) {ans ++;t3 = 0;}
            else {
                t3 += 2;
                if(t2 == 1) {ans += 2;}
                else {ans +=t3; }
            }
            t2 = t1;
        }
    }
    cout << ans <<endl;
    return 0;
}


活动打卡代码 AcWing 3227. 折点计数

凌风_5
4个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1234;
int a[N],b[N];
int main() {
    int n;
    cin >> n;
    cin >> a[0];
    for(int i = 1; i < n; i++){
        cin >> a[i];
        if(a[i] > a[i-1]) b[i] = 1;
        else b[i] = -1;
    }
    int ans = 0;
    for(int i = 0; i < n-1 ;i++){
        if(b[i] + b[i+1] == 0) ans ++;
    }
    cout <<ans << endl;
    return 0;
}


活动打卡代码 AcWing 3232. 最大波动

凌风_5
4个月前
#include <bits/stdc++.h>
using namespace std;


int main (){
    int n;
    cin >> n;
    int t1,t2 = 0,ans = -1;
    cin >> t1;t2 = t1;
    if(ans < abs(t1 - t2)) ans = abs(t1-t2);
    for(int i = 1; i < n; i++){
        cin >> t1;
        if(ans < abs(t1 - t2)) ans = abs(t1-t2);
        t2 = t1;
    }
    cout << ans<<endl;;
    return 0;
}



凌风_5
4个月前

区间合并 (差分处理)

模拟n == 1;
四个角初始:(1,-1,-1,1)

-1              1
    0   0   0   0   
    0   0   0   0   
    0   0   0   0   
    1   0   0   0   -1

0开始出发到本行-1

    -1              1
    0   0   0   0   
    0   0   0   0   
    0   0   0   0   
0   1   1   1   1   -1

-1关键点差分为0,继续到下一个-1


0   -1              1
0   1   1   1   1   0
0   1   1   1   1   0
0   1   1   1   1   0
0   1   1   1   1   0

到关键点1;

0   0   0   0   0   1
0   1   1   1   1   0
0   1   1   1   1   0
0   1   1   1   1   0
0   1   1   1   1   0

处理点1为0;

0   0   0   0   0   0
0   1   1   1   1   0
0   1   1   1   1   0
0   1   1   1   1   0
0   1   1   1   1   0
#include<iostream>

using namespace std;
const int N=15;
int p[N*5][N*10];
int n;
int main(){
    cin>>n;
    while(n--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1++,y1++;
        p[x1][y1]+=1;
        p[x2+1][y1]-=1;
        p[x1][y2+1]-=1;
        p[x2+1][y2+1]+=1;
    }

    int ans=0;

    for(int i=1;i<=51;i++)
        for(int j=1;j<=101;j++){
            p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1];
            if(p[i][j]) ans++;
        }
    cout<<ans;
    return 0;
}



活动打卡代码 AcWing 3203. 画图

凌风_5
4个月前
#include <bits/stdc++.h>

using namespace std;

int a[120][120];
int x1,x2;
int y,y2;
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> x1 >> y >> x2 >> y2;
        for(int j = x1+1; j <= x2; j++){
            for(int k = y+1; k <= y2; k++){
                a[j][k] = 1;
            }
        }
    }
    int ans = 0 ;
    for(int j = 0; j < 102; j++){
            for(int k = 0; k < 102; k++){
                if(a[j][k] ) ans ++;
            }
    }
    cout << ans <<endl;
    return 0;
}


活动打卡代码 AcWing 3208. Z字形扫描

凌风_5
4个月前
#include <bits/stdc++.h>

using namespace std;
const int N = 1000;
int main(){
    int n;
    cin >> n;
    int a[N][N];
    for(int i = 0; i < n; i++){
        for( int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }

    bool isfalse = false;
    for(int i = 0,j = 0;i < n && j < n; ){

            if(isfalse){
                while(j && i < n-1){
                    cout<< a[i][j]<< " ";j--,i++;
                }
                cout<< a[i][j] <<" ";
                if(i == n-1 && j == n -1) {i ++;j++;break;}
                if(i == n-1) j ++; 
                else i ++;
                isfalse = false;
            }

            else {
                while(i && j < n-1) {
                    cout<< a[i][j]<<" ";i --,j++; 
                }
                cout<<a[i][j]<<" ";
                if(i == n-1 && j == n -1) {i ++;j++;break;}

                if(j == n - 1) i ++;
                else j ++;
                isfalse = true;
            }

    }
    return 0;
}


活动打卡代码 AcWing 1477. 拼写正确

凌风_5
4个月前

···

include [HTML_REMOVED]

using namespace std;

string s[10] = {“zero”,”one”,”two”,”three”,”four”,”five”,”six”,”seven”,”eight”, “nine”};

int main(){
string s1 =”“;
cin >> s1;
int l = s1.length();
int ans = 0,ans1[20];
for(int i = 0; i < l; i){
int t = s1[i] - ‘0’;
ans += t;
}
int j = 0;
if(ans == 0) cout << s[0]<<” “;
while(ans){
ans1[
j] = ans%10;
ans /= 10;
}
// while(j){
// cout << ans1[j–]<<” “;
// }
while(j){
cout << s[ans1[j–]]<<” “;
}
return 0;
}
···



活动打卡代码 AcWing 445. 数字反转

凌风_5
4个月前
#include <bits/stdc++.h>
using namespace std;

int main(){
    long long n,ans= 0;
    cin >>n;
    if(n< 0){n = -n;cout<<"-";}
    while(n) {
        ans = ans *10 + n%10;
        n /= 10;
    }
    cout<<ans<<endl;
    return 0;
}