头像

_XY_

ZJ




离线:10天前


最近来访(36)
用户头像
zhyou
用户头像
JXUCM主将从现
用户头像
面条小王子
用户头像
lgvc
用户头像
Joe0927
用户头像
0x37.
用户头像
东方蒟蒻
用户头像
cxy660102
用户头像
SEEK
用户头像
Jack404
用户头像
植树的da.lad.la
用户头像
小学生kksk
用户头像
QRMeng
用户头像
OI
用户头像
宇宙无敌大帅哥
用户头像
zhang_6
用户头像
Oier12138
用户头像
Kurumi
用户头像
kobe88
用户头像
nyj


_XY_
10天前

#include<bits/stdc++.h> using namespace std; int t; int main() { cin>>t; while(t--){ long long a,b=0; cin>>a; while(a){ if(a%2==1)b++; a/=2; } b=pow(2,b); cout<<b<<endl; } return 0; }




_XY_
2021-05-11 12:44


新鲜事 原文

_XY_
2021-05-11 12:41
@精神小伙,他抄袭!
图片



_XY_
2021-05-11 07:51

边输入边处理字符串,用stl的map[HTML_REMOVED]可以统计每个字符出现的次数,然后实时更新maxn;注意:,minn要在字符串输入完之后在遍历更新,不然会是1;处理完后剩下的素数判断就简单了;

#include<bits/stdc++.h>  //万能头文件
using namespace std;
int primenum(int m);  //质数的判断
int main()
{
    char ch[1000];
    int array[100]={0};
    int m,n,i,j,k;
    int maxn=-500,minn=9999;
    scanf("%s",ch);
    for(int m=0;m<strlen(ch);m++){
        array[ch[m]-'a']++;
    }
    for(int m=0;m<26;m++){
        if(array[m]>maxn&&array[m]!=0) maxn=array[m];
        if(array[m]<minn&&array[m]!=0) minn=array[m];
    }
    if(primenum(maxn-minn)){
        printf("Lucky Word\n%d",maxn-minn);
    }else{
        printf("No Answer\n0");
    }
}
int primenum(int m)
{
    int i;
    if(m==2||m==3)  return 1;
    if(m==1||m==0)  return 0;
    if(m%6!=1&&m%6!=5) return 0;  //优化质数的判断方法
    for(i=5;i<=sqrt(m);i+=5){
        if(m%i==0||m%(i+2)==0){
            return 0;
        }
    }
    return 1;
}



_XY_
2021-05-10 17:19

问题描述
会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。 对于某个满足要求的8皇后的摆放方法,定义一个皇后串a与之对应,即a=b1b2…b8,其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解(即92个不同的皇后串)。给出一个数b,要求输出第b个串。串的比较是这样的:皇后串x置于皇后串y之前,当且仅当将x视为整数时比y小。
输入数据
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数b(1 <= b <= 92)
输出要求
n行,每行输出对应一个输入。输出应是一个正整数,是对应于b的皇后串
输入样例
2
1
92

输出样例
15863724
84136275

解题思路一
因为要求出92种不同摆放方法中的任意一种,所以我们不妨把92种不同的摆放方法一次性求出来,存放在一个数组里。为求解这道题我们需要有一个矩阵仿真棋盘,每次试放一个棋子时只能放在尚未被控制的格子上,一旦放置了一个新棋子,就在它所能控制的所有位置上设置标记,如此下去把八个棋子放好。当完成一种摆放时,就要尝试下一种。若要按照字典序将可行的摆放方法记录下来,就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试;对于第一个棋子的每一个位置,将第二个棋子从可行的位置从小到大的顺序尝试;在第一第二个棋子固定的情况下,将第三个棋子从可行的位置从小到大的顺序尝试;依次类推。
首先,我们有一个8*8的矩阵仿真棋盘标识当前已经摆放好的棋子所控制的区域。用一个有92行每行8个元素的二维数组记录可行的摆放方法。用一个递归程序来实现尝试摆放的过程。基本思想是假设我们将第一个棋子摆好,并设置了它所控制的区域,则这个问题变成了一个7皇后问题,用与8皇后同样的方法可以获得问题的解。那我们就把重心放在如何摆放一个皇后棋子上,摆放的基本步骤是:从第1到第8个位置,顺序地尝试将棋子放置在每一个未被控制的位置上,设置该棋子所控制的格子,将问题变为更小规模的问题向下递归,需要注意的是每次尝试一个新的未被控制的位置前,要将上一次尝试的位置所控制的格子复原。

参考程序一
[cpp] view plain copy

#include <stdio.h>  
#include <math.h>  
int queenPlaces[92][8]; //存放92种皇后棋子的摆放方法  
int count = 0;  
int board[8][8]; //仿真棋盘  
void putQueen(int ithQueen); //递归函数,每次摆好一个棋子  

void main()  
{  
   int n, i, j;    
    for(i = 0; i < 8; i++){  // 初始化  
        for(j = 0; j < 8; j++)  
            board[i][j] = -1;  
        for(j = 0; j < 92; j++)  
            queenPlaces[j][i] = 0;  
    }  
    putQueen(0); //从第0个棋子开始摆放,运行的结果是将queenPlaces生成好  
   scanf(”%d”, &n);  
   for(i = 0; i < n; i++){  
        int ith;  
        scanf(”%d”, &ith);  
        for(j = 0; j < 8; j++)  
           printf(”%d”, queenPlaces[ith - 1][j]);  
        printf(”\n”);  
    }  
}  
void putQueen(int ithQueen){  
     int i, k, r;  
     if(ithQueen == 8){  
         count ++;  
         return;  
     }  
     for(i = 0; i < 8; i++){  
         if(board[i][ithQueen] == -1){  
             //摆放皇后  
             board[i][ithQueen] = ithQueen;  
             //将其后所有的摆放方法的第ith个皇后都放在i+1的位置上  
             //在i增加以后,后面的第ith个皇后摆放方法后覆盖此时的设置  
             for(k = count; k < 92; k++)  
                 queenPlaces[k][ithQueen] = i + 1;  
             //设置控制范围  
             for(k = 0; k < 8; k++)  
             for(r = 0; r < 8; r++)  
                 if(board[k][r] == -1 &&   
                     (k == i || r == ithQueen || abs(k - i) == abs(r - ithQueen)))   
                     board[k][r] = ithQueen;  
             //向下级递归  
             putQueen(ithQueen + 1);  
             //回溯,撤销控制范围  
             for(k = 0; k < 8; k++)  
             for(r = 0; r < 8; r++)  
                     if(board[k][r] == ithQueen) board[k][r] = -1;  
         }  
     }  
}  

解题思路二
上面的方法用一个二维数组来记录棋盘被已经放置的棋子的控制情况,每次有新的棋子放置时用了枚举法来判断它控制的范围。还可以用三个一维数组来分别记录每一列,每个45度的斜线和每个135度的斜线上是否已经被已放置的棋子控制,这样每次有新的棋子放置时,不必再搜索它的控制范围,可以直接通过三个一维数组判断它是否与已经放置的棋子冲突,在不冲突的情况下,也可以通过分别设置三个一维数组的相应的值,来记录新棋子的控制范围。

参考程序二

#include <stdio.h>
int  record[92][9], mark[9], count = 0; //record记录全部解,mark记录当前解;
bool range[9], line1[17], line2[17]; //分别记录列方向,45度,135度方向上被控制的情况
void tryToPut(int ); //求全部解的过程
void main()
{
    int i, testtimes, num;
    scanf("%d", &testtimes);

    for(i = 0; i <=8; i++)
        range[i] = true;
    for(i = 0; i < 17; i ++)
        line1[i] = line2[i] = true;

    tryToPut(1);

    while(testtimes --){
        scanf("%d", &num);
        for(i = 1; i <=8; i++)
            printf("%d", record[num - 1][i]);
        printf("\n");
    }
}

void tryToPut(int i){
    if(i > 8){ //如果最后一个皇后被放置完毕,将当前解复制到全部解中
        for(int k = 1; k < 9; k ++) 
            record[count][k] = mark[k];
        count ++;
     }                  
     for(int j=1; j<=8; j++){ 逐一尝试将当前皇后放置在不同列上
         if(range[j] && line1 [i + j] && line2[i - j + 9]){ //如果与前面的不冲突,
                                               //则把当前皇后放置在当前位置
            mark[i] = j;
            range[j] = line1[i + j] = line2[i - j + 9] = false;
            tryToPut(i + 1);
            range[j] = line1[i + j] = line2[i - j + 9] = true;
        }
    }
}```
解题思路三
这个题目也可以不用仿真棋盘来模拟已放置棋子的控制区域,而只用一个有8个元素的数组记录已经摆放的棋子摆在什么位置,当要放置一个新的棋子时,只需要判断它与已经放置的棋子之间是否冲突就行了。


参考程序三

include [HTML_REMOVED]

int ans[92][8], n, b, i, j, num, hang[8];

void queen(int i){

int j, k;

if(i == 8){ //一组新的解产生了

    for(j = 0; j < 8; j++)  ans[num][j] = hang[j] + 1;

    num++;

    return;

}

for (j=0; j<8; j++){ //将当前皇后i逐一尝试放置在不同的列

    for(k=0; k<i; k++) //逐一判定i与前面的皇后是否冲突

        if( hang[k] == j || (k - i) == (hang[k] - j) || (i - k) == (hang[k] - j )) break;

    if (k == i) {  //放置i,尝试第i+1个皇后

        hang[i] = j;

        queen(i + 1);

    }

}

}

void main( ){

num=0;

queen(0);

scanf(“%d”, &n);

for(i = 0; i < n; i++){

    scanf(“%d”, &b);

    for(j = 0; j < 8; j++)  printf(“%d”, ans[b - 1][j]);

    printf(“\n”);

}

}
```
实现中常见的问题
问题一: 使用枚举法,穷举8个皇后的所有可能位置组合,逐一判断是否可以互相被吃掉,得到超时错误;
问题二:对于多组输入,有多组输出,没有在每组输出后加换行符,得到格式错;
问题三:对输入输出的函数不熟悉,试图将数字转换成字符或者将8个整数转换成8位的十进制整数来完成输出,形成不必要的冗余代码。




_XY_
2021-05-10 17:12

算法1

题目描述:

给出n,表示在2*n个空位上填(或),使得整个序列是合法的。问总共有多少种方案。

分析:
显然裸裸的搜索是可以的,但是效率比较低。

如果我们定义状态f[i][j],表示前i个空位,还需j个)就是合法序列的方案数。那么就很简单了,f[i][j]=f[i-1][j-1]+f[i-1][j+1]。

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=110;
long long f[maxn][maxn];
bool a[maxn];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    memset(a,0,sizeof(a));
    for (int i=0;i<m;i++){
        int x;
        scanf("%d",&x);
        a[x]=1;
    }
    f[0][0]=1;
    for (int i=1;i<=2*n;i++)
        for (int j=0;j<=n;j++)
            if (a[i]){if (!j)f[i][j]+=f[i-1][j-1];}
            else{
                if (j)f[i][j]+=f[i-1][j-1];
                if (j<n)f[i][j]+=f[i-1][j+1];
            }
    printf("%lld",f[2*n][0]);
    return 0;
}

算法2

solution

首先我们考虑暴力每一个起点,用栈维护。当栈为空时,满足j~i为合法的位置。

效率O(n^2)

那么显然是T了,我们考虑从头开始只维护一个栈,记录下每一个位置的栈的状态。

状态用hash值表示

显然相同状态的栈可以互相贡献,那我们排序一下,统计就行。

C++ 代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll unsigned long long
#define p 998244353
#define maxn 1000006
using namespace std;
int n,id[maxn],top;
char ch[maxn],zh[maxn];
ll s[maxn];
int main()
{
    scanf("%s",ch+1);
    s[0]=0;n=strlen(ch+1);
    for(int i=1;i<=n;i++){
        if(top>0&&ch[i]==zh[top]){
            s[i]=s[id[top]];top--;
        }
        else {
            zh[++top]=ch[i];id[top]=i-1;
            s[i]=s[i-1]*p+ch[i];
        }
    }
    //for(int i=0;i<=n;i++)cout<<s[i]<<endl;
    sort(s,s+n+1);
    int i=0;
    long long ans=0;
    while(i<=n){
        int j=i;while(s[j]==s[i]&&j<=n)j++;
        int l=j-i;
        ans=ans+(1LL)*l*(l-1)/2;
        i=j;
    }
    cout<<ans<<endl;
    return 0;
}



_XY_
2021-05-10 17:02

算法1

(暴力枚举)

时间复杂度 $O(n^2)$


算法1

(暴力枚举) $O(n^2)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    unsigned long long a,n,sum=1;
    cin>>n>>a;
    for(unsigned long long i=2;i<=n;i++)
        sum*=i;
    for(unsigned long long k=n;k>=1;k--)
    {
        long long b=pow(a,k),c=pow(a,k+1); 
        if(sum%b==0&&sum%c!=0)
        {
            cout<<k;
            break;
        }
    } 
    return 0;
}



_XY_
2021-05-10 16:44

#include<bits/stdc++.h> using namespace std; int t; int main() { cin>>t; while(t--){ long long a,b=0; cin>>a; while(a){ if(a%2==1)b++; a/=2; } b=pow(2,b); cout<<b<<endl; } return 0; }




_XY_
2021-05-10 16:40

题目描述

求A+B,A-B,A*B的值

算法1

(c++)

万能头

#include<bits/stdc++.h>

C++ 代码

#include<iostream>
using namespace std;
int main()
{
    unsigned long long a,b;
    cin>>a>>b;
    cout<<a+b<<endl;
    cout<<a-b<<endl;
    cout<<a*b;
    return 0;
}

算法2

(python)

基本输入输出

input()
print()

python 代码

i=input()
j=input()
print(i+j)
print(i-j)
print(i*j)



_XY_
2021-05-10 12:14

® 运算忽略参与运算的字母的大小写,并保持字母在明文 MM 中的大小写形式;
当明文 MM 的长度大于密钥 kk 的长度时,将密钥 kk 重复使用。 例如,明文 M=M=Helloworld,密钥 k=k=abc时,密文 C=C=Hfnlpyosnd。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string k,c;
char ans;
int tip=0,t,f,a[150];
int main()  
{     
   ios::sync_with_stdio(false);
   cin>>k>>c;
   for(int i=0;i<k.length();i++)
   {
    if(k[i]>='a'&&k[i]<='z') a[i]=k[i]-'a';
    else a[i]=k[i]-'A'; 
   }
   for(int i=0;i<c.length();i++)
   {
    if(c[i]>='a'&&c[i]<='z') f=0,t=c[i]-'a';
    else f=1,t=c[i]-'A';
    t-=a[tip];
    if(t<0) t+=26;
    if(f) ans='A'+t;
    else ans='a'+t;
    cout<<ans;
    tip++;
    if(tip>=k.length()) tip=0;
   }
   return 0;  
}