H题
题意
统计1~n“k合因子数”数量。一个数的k合因子数是指这个数所有是合数的因子的数量。
思路
使用埃氏筛标记出来[1,n]所有的合数，因为埃氏筛的模板是标记质数，要特别注意1和0既不是质数又不是合数，所以记得要改一下标记。
完成了这一步以后，我们得到一个[1,n]是否是合数的bool数组chk，要鉴别一个数x是否是合数，只需要查chk[x]即可。
然后逐个检索每个合数，得到它们的因数个数，再减去其中非因数的即可。
其实我前一个小时一直在想这题，确切的说是一直在胡思乱想，我总觉得有更好的更优美的写法，可以直接一步到位。
就是模仿欧拉筛：简单说一下，埃氏筛是筛掉所有质数的倍数，欧拉筛加了一个“不重复访问”。对于这道题而言，任何一个合数都可以表示成为若干个质数的积，那么在出质数的时候就可以递推，比如2是一个质数， 不是质数，并且
多了一个因子，
多了两个因子，
多了两个因子并且拥有4的所有因子（这里可以考虑去重但是好像没必要。
可能等我有空（）会再写一下吧。
我的代码
solution
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
bool chk[N+1];
int cnt[N];
void sieve(int n) {//埃筛
int p = 0;
for(int i = 0; i <= n; i++) chk[i] = 1;
chk[0] = chk[1] = 0;
for(int i = 2; i <= n; i++)
if(chk[i]) {
chk[p++] = i;
for(int j = 2*i; j <= n; j+=i) chk[j] = 0; //筛去所有质数的倍数
}
}
int f(int num) {//判断合因数个数
int factor[1600],m=0;
for(int i=1; i<=num/i; i++)
if(num%i==0) {
factor[++m]=i;
if(i!=num/i)factor[++m]=num/i;
}
int ans=m;
for(int i=1; i<=m; i++)
if(chk[factor[i]]) ans--;
return ans;
}
int main() {
int n,m;
cin>>n>>m;
sieve(n);
chk[0]=1,chk[1]=1;
for(int i=4; i<=n; i++) {
if(!chk[i]) cnt[f(i)]++;
}
int k;
while(m--){
cin>>k;
cout<<cnt[k]<<endl;
}
return 0;
}埃筛模板
#include <iostream>
using namespace std;
const int N = 10005;
int prime[N]; //第i个素数
bool is_prime[N+1]; //is_prime[i]为true时表示i是素数
int sieve(int n) {//返回n以内素数的个数
int p = 0;
for(int i = 0; i <= n; i++) is_prime[i] = true;
is_prime[0] = is_prime[1] = false;
for(int i = 2; i <= n; i++) {
if(is_prime[i]) {
prime[p++] = i;
for(int j = 2*i; j <= n; j+=i) is_prime[j] = false; //筛去所有素数的倍数
}
}
return p;
}
int main() {
int n; //枚举n以内素数
while(cin>>n) {
int p = sieve(n);
cout<<p<<endl;
for(int i = 0; i < p; i++)
cout<< prime[i]<<" ";
cout<<endl;
}
return 0;
}判断因数个数模板
int work(int num){
int factor[1600],m=0;
for(int i=1;i<=num/i;i++){
if(num%i==0){
factor[++m]=i;
if(i!=num/i)factor[++m]=num/i;
}
}
return m;
}别人的代码
最短的
#include <iostream>
using namespace std;
int a[100010],b[100010];
int main(){
int n,m,k;
cin>>n>>m;
for(int i=2;i<=n;i++)
for(int j=i+i;j<=n;j+=i)
if(a[j]==0 || a[i]!=0) a[j]++;
for(int i=0;i<=n;i++) b[a[i]]++;
while(m--){
cin>>k;
cout<<b[k]<<endl;
}
return 0;
}xby大佬的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
bool vis[maxn];
ll ans[maxn],res[maxn];
int n,m;
void solve(int x) {
int tmp=x,cnt=0;
for(int i=1; i*i<=x; i++) {
if( x%i==0 ) {
if(vis[i]==1) cnt++;
if(i*i!=x && vis[x/i]==1) cnt++;
}
}
ans[cnt]++;
}
int main() {
for(int i=2; i<2e5; i++)
for(int j=i+i; j<2e5; j+=i) vis[j]=1;
cin>>n>>m;
for(int i=1; i<=n; i++) solve(i);
for(int i=1; i<=m; i++) cin>>res[i];
for(int i=1; i<=m; i++) cout<<ans[res[i]]<<endl;
}ylm大佬的
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
bool v[n+1]={0};
for(int i=2;i<=n;i++){
if(v[i])continue;
for(int j=i;j<=n/i;j++)v[i*j]=1;
}
int nums[n+1]={0},ans[n+1]={0};
for(int i=1;i<=n;i++)
for(int j=1;j<=n/i;j++)
if(v[i]) nums[i*j]++;
for(int i=1;i<=n;i++)
ans[nums[i]]++;
while(m--){
int k;
cin>>k;
cout<<ans[k]<<endl;
}
}I题
题意
汉诺塔，输入n，统计A->B,A->C,B->A,B->C,C->A,C->B的次数，以及所有移动的总步数。
思路
编码小问题
总的移动步数肯定是,但是我用pow函数wa了好几次，非常不满。
我还想到了两种表示方案：第一种是直接六个数加起来，第二种是使用移位运算符
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int main() {
ll a=(1<<60)-1;
cout<<a<<endl;
return 0;
}
//输出结果：18446744073709551615需要注意的是因为移位运算符和流使用的是一种符号所以不能写在cout里面。
试了一下这种表示形式可以表示到ull的上限。
我的思路
我的做法就是找规律+部分打表+递推。
我先用模拟的代码（一定超时，要到60的话一下午都模拟不完）
#include <bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
unsigned long long counter[10];
void Move(char g,char p) {
if(g=='a'&&p=='b')counter[0]++;
else if(g=='a'&&p=='c') counter[1]++;
else if(g=='b'&&p=='a') counter[2]++;
else if(g=='b'&&p=='c') counter[3]++;
else if(g=='c'&&p=='a') counter[4]++;
else if(g=='c'&&p=='b') counter[5]++;
}
void h(int n,char a,char b,char c) {
if(n==1)
Move(a,c);
else {
h(n-1,a,c,b);
Move(a,c);
h(n-1,b,a,c);
}
}
int main() {
// int m;
// while(~scanf("%d",&m)){
for(int i=1; i<=20; i++) {
memset(counter,0,sizeof(counter));
h(i,'a','b','c');
printf("%llu,",counter[0]);
printf("%llu,",counter[1]);
printf("%llu,",counter[2]);
printf("%llu,",counter[3]);
printf("%llu,",counter[4]);
printf("%llu\n",counter[5]);
}
return 0;
}可以输出n在[1,20]里对应的答案。
观察可以发现每个从偶数n-1变成奇数n的过程，SUM+2^(n-1),且AB BC CA三项不变，AC BA CB有变化，且BA一直等于CB，且二者变化的差值为1。从奇数到偶数也是类似的。
所以我把它们的差值用excel算了一下，每一组分成大值和小值，发现它们是“循环翻倍”的关系，那么到了这一步，我们只需要知道前几组数据，就可以推出来后面的所有数据的之间的变化差值，进而得到所有的数据。（就不用模拟了）。
大佬的补充
A->B=（上一次）A->C->B
B->C=（上一次）B->A->C
C->A=（上一次）C->B->A
另外居然有大佬用dp做，菜鸡大概暂时理解不了https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42887735
我的代码
solution
#include <bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int N = 1e5+7;
unsigned long long ad[61][2]= {0};
unsigned long long ans[61][6]= {0,0,0,0,0,0, 0,1,0,0,0,0, 1,1,0,1,0,0, 1,3,1,1,0,1, 4,3,1,4,2,1};
int main() {
ad[3][0]=2;
ad[3][1]=1;
ad[4][0]=3;
ad[4][1]=2;
for(int i=5; i<=60; i++) {
if(i&1) {
ad[i][0]=ad[i-1][0]*2;
ad[i][1]=ad[i][0]-1;
} else {
ad[i][1]=ad[i-1][1]*2;
ad[i][0]=ad[i][1]+1;
}
}
for(int i=5; i<=60; i++) {
if(i&1) {
ans[i][0]=ans[i-1][0];
ans[i][1]=ans[i-1][1]+ad[i][0];
ans[i][2]=ans[i-1][2]+ad[i][1];
ans[i][3]=ans[i-1][3];
ans[i][4]=ans[i-1][4];
ans[i][5]=ans[i-1][5]+ad[i][1];
} else {
ans[i][0]=ans[i-1][0]+ad[i][0];
ans[i][1]=ans[i-1][1];
ans[i][2]=ans[i-1][2];
ans[i][3]=ans[i-1][3]+ad[i][0];
ans[i][4]=ans[i-1][4]+ad[i][1];
ans[i][5]=ans[i-1][5];
}
}
int n;
while(cin>>n) {
printf("A->B:%llu\n",ans[n][0]);
printf("A->C:%llu\n",ans[n][1]);
printf("B->A:%llu\n",ans[n][2]);
printf("B->C:%llu\n",ans[n][3]);
printf("C->A:%llu\n",ans[n][4]);
printf("C->B:%llu\n",ans[n][5]);
cout<<"SUM:"<<ans[n][0]+ans[n][1]+ans[n][2]+ans[n][3]+ans[n][4]+ans[n][5]<<endl;
}
return 0;
}顺便一提，我中间又越界了，所以数组一定要开大一点啊。
你可以看到这个循环体里只有对数据的调用，数据的处理过程其实是已经打好了表的，然后我让他们打表他们一个都没打杨文冠打了，点名表扬。
打表
#include <bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
using namespace std;
unsigned long long ans[61][6]= {0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,1,0,0,1,3,1,1,0,1,4,3,1,4,2,1,4,9,6,4,2,6,15,9,6,15,12,6,15,31,27,15,12,27,58,31,27,58,54,27,58,117,112,58,54,112,229,117,112,229,224,112,229,459,453,229,224,453,912,459,453,912,906,453,912,1825,1818,912,906,1818,3643,1825,1818,3643,3636,1818,3643,7287,7279,3643,3636,7279,14566,7287,7279,14566,14558,7279,14566,29133,29124,14566,14558,29124,58257,29133,29124,58257,58248,29124,58257,116515,116505,58257,58248,116505,233020,116515,116505,233020,233010,116505,233020,466041,466030,233020,233010,466030,932071,466041,466030,932071,932060,466030,932071,1864143,1864131,932071,932060,1864131,3728274,1864143,1864131,3728274,3728262,1864131,3728274,7456549,7456536,3728274,3728262,7456536,14913085,7456549,7456536,14913085,14913072,7456536,14913085,29826171,29826157,14913085,14913072,29826157,59652328,29826171,29826157,59652328,59652314,29826157,59652328,119304657,119304642,59652328,59652314,119304642,238609299,119304657,119304642,238609299,238609284,119304642,238609299,477218599,477218583,238609299,238609284,477218583,954437182,477218599,477218583,954437182,954437166,477218583,954437182,1908874365,1908874348,954437182,954437166,1908874348,3817748713,1908874365,1908874348,3817748713,3817748696,1908874348,3817748713,7635497427,7635497409,3817748713,3817748696,7635497409,15270994836,7635497427,7635497409,15270994836,15270994818,7635497409,15270994836,30541989673,30541989654,15270994836,15270994818,30541989654,61083979327,30541989673,30541989654,61083979327,61083979308,30541989654,61083979327,122167958655,122167958635,61083979327,61083979308,122167958635,244335917290,122167958655,122167958635,244335917290,244335917270,122167958635,244335917290,488671834581,488671834560,244335917290,244335917270,488671834560,977343669141,488671834581,488671834560,977343669141,977343669120,488671834560,977343669141,1954687338283,1954687338261,977343669141,977343669120,1954687338261,3909374676544,1954687338283,1954687338261,3909374676544,3909374676522,1954687338261,3909374676544,7818749353089,7818749353066,3909374676544,3909374676522,7818749353066,15637498706155,7818749353089,7818749353066,15637498706155,15637498706132,7818749353066,15637498706155,31274997412311,31274997412287,15637498706155,15637498706132,31274997412287,62549994824598,31274997412311,31274997412287,62549994824598,62549994824574,31274997412287,62549994824598,125099989649197,125099989649172,62549994824598,62549994824574,125099989649172,250199979298369,125099989649197,125099989649172,250199979298369,250199979298344,125099989649172,250199979298369,500399958596739,500399958596713,250199979298369,250199979298344,500399958596713,1000799917193452,500399958596739,500399958596713,1000799917193452,1000799917193426,500399958596713,1000799917193452,2001599834386905,2001599834386878,1000799917193452,1000799917193426,2001599834386878,4003199668773783,2001599834386905,2001599834386878,4003199668773783,4003199668773756,2001599834386878,4003199668773783,8006399337547567,8006399337547539,4003199668773783,4003199668773756,8006399337547539,16012798675095106,8006399337547567,8006399337547539,16012798675095106,16012798675095078,8006399337547539,16012798675095106,32025597350190213,32025597350190184,16012798675095106,16012798675095078,32025597350190184,64051194700380397,32025597350190213,32025597350190184,64051194700380397,64051194700380368,32025597350190184,64051194700380397,128102389400760795,128102389400760765,64051194700380397,64051194700380368,128102389400760765,256204778801521560,128102389400760795,128102389400760765,256204778801521560,256204778801521530,128102389400760765};
int main() {
int n;
while(cin>>n) {
printf("A->B:%llu\n",ans[n][0]);
printf("A->C:%llu\n",ans[n][1]);
printf("B->A:%llu\n",ans[n][2]);
printf("B->C:%llu\n",ans[n][3]);
printf("C->A:%llu\n",ans[n][4]);
printf("C->B:%llu\n",ans[n][5]);
unsigned long long a=(1<<n)-1;
cout<<"SUM:"<<ans[n][0]+ans[n][1]+ans[n][2]+ans[n][3]+ans[n][4]+ans[n][5]<<endl;
}
return 0;
}写到这里发现好像移位运算符用不了
编译器似乎也报错移位长度大于类型位数。但是llu不是64位存储吗，拿这样的话就没办法使用移位来表示了？？？
我看了青竹大佬的代码明白了
ll sum = (1LL<<i) - 1;
这样就没有问题了。
（小声吐槽一下xby大佬和青竹大佬的代码一模一样。
别人的代码
最短的递推
#include <iostream>
using namespace std;
typedef unsigned long long ll;
ll q[3][3]= {0};
ll m=0,n=0,p=0,c=1,x;
int main() {
cin>>x;
for (ll i=2; i<=x; i++) {
if (i&1) {
n=m+p;
c=p+p+1;
}else{
p=n+c;
m=n+n;
}
}
cout<<"A->B:"<<p<<'\n';
cout<<"A->C:"<<c<<'\n';
cout<<"B->A:"<<n<<'\n';
cout<<"B->C:"<<p<<'\n';
cout<<"C->A:"<<m<<'\n';
cout<<"C->B:"<<n<<'\n';
cout<<"SUM:"<<(1LL<<x)-1<<endl;
}记忆化搜索标程
（出题人的代码 本菜鸡看不懂）
#include<bits/stdc++.h>
using namespace std;
struct node {
long long data[6];
node() {
memset(data,0,sizeof(data));
}
//A->B 0
//A->C 1
//B->A 2
//B->C 3
//C->A 4
//C->B 5
};
node operator + (const node &A,const node &B) {
node C;
for(int i=0; i<6; ++i) {
C.data[i]=A.data[i]+B.data[i];
}
return C;
}
void moveto(int x,int y,node &temp) {
if(x==0&&y==1)++temp.data[0];
if(x==0&&y==2)++temp.data[1];
if(x==1&&y==0)++temp.data[2];
if(x==1&&y==2)++temp.data[3];
if(x==2&&y==0)++temp.data[4];
if(x==2&&y==1)++temp.data[5];
return;
}
node dp[3][3][3][105];
bool vis[3][3][3][105];
node hanoi(int a,int b,int c,int n) {
if (vis[a][b][c][n])return dp[a][b][c][n];
if (n==1) {
moveto(a,c,dp[a][b][c][n]);
vis[a][b][c][n]=true;
return dp[a][b][c][n];
}
node temp;
temp=temp+hanoi(a,c,b,n-1);
moveto(a,c,temp);
temp=temp+hanoi(b,a,c,n-1);
vis[a][b][c][n]=true;
return dp[a][b][c][n]=temp;
}
int n;
int main() {
scanf("%d",&n);
node ans=hanoi(0,1,2,n);
printf("A->B:%lld\n",ans.data[0]);
printf("A->C:%lld\n",ans.data[1]);
printf("B->A:%lld\n",ans.data[2]);
printf("B->C:%lld\n",ans.data[3]);
printf("C->A:%lld\n",ans.data[4]);
printf("C->B:%lld\n",ans.data[5]);
printf("SUM:%lld\n",(1LL<<n)-1);
}A题
题意
RBD三种格子，R右D下B都可以，看似走迷宫实际上并不是BFS，他要求统计种数，而且没有严格意义上的死路。思路就是DP，就不写了。
代码
#include<bits/stdc++.h>
using namespace std;
long long a[55][55],mod=1e9+7;
char s[55];
int main(){
int n,m,i,j;
cin>>n>>m;
a[1][1]=1;
for(i=1;i<=n;i++){
cin>>s+1;
for(j=1;j<=m;j++){
if(s[j]=='D'||s[j]=='B')
a[i+1][j]+=a[i][j],a[i+1][j]%=mod;
if(s[j]=='R'||s[j]=='B')
a[i][j+1]+=a[i][j],a[i][j+1]%=mod;
}
}
cout<<a[n][m];
return 0;
}CD弱智签到题居然一开始没写……
D题
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int a[100005];
map<int,int>f;
int main(){
int n,size=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[a[i]]=i;
size=max(size,a[i]);
}
printf("The size of the tree is %d\n",size);
printf("Node %d is the root node of the tree\n",a[1]);
for(int i=1;i<=size;i++){
printf("The father of node %d is %d,",i,(f[i]/2>=1?a[f[i]/2]:-1));
printf(" the left child is %d,",(2*f[i]<=n?a[2*f[i]]:-1));
printf(" and the right child is %d\n",(2*f[i]+1<=n?a[2*f[i]+1]:-1));
}
}#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int pos[1000005];
int n;
int main(){
memset(a,-1,sizeof(a));
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
ans+=(a[i]!=-1);
pos[a[i]]=i;
}
printf("The size of the tree is %d\n",ans);
printf("Node %d is the root node of the tree\n",a[1]);
for(int i=1;i<=ans;i++){
printf("The father of node %d is %d, the left child is %d, and the right child is %d\n",i,a[pos[i]/2],a[pos[i]*2],a[pos[i]*2+1]);
}
}F题
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main() {
long long n,ans=0,cnt=0,num=0;
string s;
cin>>n>>s;
for(int i=0;i<n;i++){
if(s[i]=='1') num++,ans+=cnt;
cnt+=num;
}
cout<<ans%mod<<endl;
}
京公网安备 11010502036488号