Problem A
https://ac.nowcoder.com/acm/contest/554/A
题解：
找规律
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans[N],cnt,flag,temp,sum;
int a[N][N][N*N];
char str;
struct node{};
void add (int b[],int c[]){
int x=max(b[0],c[0]);
for(int i=1;i<=x;i++){
b[i]=b[i]+c[i];
}
for(int i=1;i<=x+100;i++){
if(b[i]>=10){
b[i+1]+=b[i]/10;
b[i]%=10;
}
if(b[i]){
b[0]=max(b[0],i);
}
}
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
a[1][1][0]=1;
a[1][0][0]=1;
a[1][1][1]=1;
a[1][0][1]=1;
for(int i=2;i<=n;i++){
a[i][0][0]=1;
a[i][0][1]=1;
for(int j=1;j<=i;j++){
for(int k=0;k<=j;k++){
add(a[i][j],a[i-1][k]);
}
//printf("%d%c",a[i][j]," \n"[i==j]);
}
}
ans[0]=1;
for(int i=1;i<=n;i++){
add(ans,a[n][i]);
}
for(int i=ans[0];i>=1;i--)
printf("%d",ans[i]);
cout<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem B
https://ac.nowcoder.com/acm/contest/554/B
题解：
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=10+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N][N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
//scanf("%d",&n);
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
scanf("%d",&a[i][j]);
}
}
ans=a[0][0]*a[1][1]*a[2][2]+a[1][0]*a[2][1]*a[0][2]+a[2][0]*a[0][1]*a[1][2]-a[0][2]*a[1][1]*a[2][0]-a[1][2]*a[2][1]*a[0][0]-a[2][2]*a[0][1]*a[1][0];
cout<<(ll)ans*ans<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem C
https://ac.nowcoder.com/acm/contest/554/C
题解：快速幂
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a,b;
char str;
struct node{};
int PowerMod(int a, int b, int c){
int ans = 1;
a = a % c;
while(b>0){
if(b % 2 == 1)
ans = (ans * a) % c;
b >>= 1;
a = (a * a) % c;
}
return ans;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&a,&n,&b);
cout<<PowerMod(a,n,b)<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem D
https://ac.nowcoder.com/acm/contest/554/D
题解：
Problem E
https://ac.nowcoder.com/acm/contest/554/E
题解：朴素
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a,b,c,y;
char str;
struct node{};
bool check(int y){
return y%4==0&&y%100!=0||y%400==0;
}
int mo[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},
{0,31,29,31,30,31,30,31,31,30,31,30,31}};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
while(~scanf("%d%d%d%d",&a,&b,&c,&y)){
int week=1;
int num=1;
ans=0;
int year,month,day;
for(int i=1850;i<=y;i++){
int f=check(i);
for(int j=1;j<=12;j++){
num=0;
for(int k=1;k<=mo[f][j];k++){
week++;
if(week>7)
week=1;
if(week==c)
num++;
if(i==y&&j==a&&b==num&&week==c){
ans=1;
year=i;
month=j;
day=k;
break;
}
}
}
}
if(ans){
printf("%d/",year);
if(month<10)
printf("0%d/",month);
else
printf("%d/",month);
if(day<10)
printf("0%d\n",day);
else
printf("%d\n",day);
}else{
cout<<"none"<<endl;
}
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem F
https://ac.nowcoder.com/acm/contest/554/F
题解：
Problem G
https://ac.nowcoder.com/acm/contest/554/G
题意：原题 求区间内 能被 自己每位上的和整除（即模 ==0）的个数
题解：
枚举每位上的和 MOD 取值[1,81]
就转化为 区间内 能被 MOD整除以及 每位上的和等于MOD 的个数
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#define cler(arr, val) memset(arr, val, sizeof(arr))
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define IN freopen ("in.txt" , "r" , stdin);
#define OUT freopen ("out.txt" , "w" , stdout);
typedef long long LL;
const int MAXN = 510011;
const int MAXM = 6000010;
const int INF = 0x3f3f3f3f;
const LL mod = 2147483647;
const double eps= 1e-8;
const double pi=acos(-1.0);
#define lson l,m, rt<<1
#define rson m+1,r,rt<<1|1
int f[10][82][82][82];
int dig[12],len;
//f[i][sum][mod][nowmod];
int dfs(int pos,int sum,int mod,int nowmod,int limit)
{
if (pos<0)
return sum==nowmod&&mod==0;
if (!limit&&f[pos][sum][mod][nowmod]!=-1)
return f[pos][sum][mod][nowmod];
int res=0;
int last=limit?dig[pos]:9;
for (int i=0;i<=last;i++)
{
int temp=(mod*10+i)%nowmod;
res+=dfs(pos-1,sum+i,temp,nowmod,limit&&(i==last));
}
if (!limit) f[pos][sum][mod][nowmod]=res;
return res;
}
int solve(int n)
{
len=0;
while(n)
{
dig[len++]=n%10;
n/=10;
}
int ans=0;
for(int i=1;i<=81;i++)
ans+=dfs(len-1,0,0,i,1);
return ans;
}
int main()
{
int n,cas=1;
cler(f,-1);
cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
if(a>b) swap(a,b);
printf("Case %d: %d\n",cas++,solve(b)-solve(a-1));
}
return 0;
} Problem H
https://ac.nowcoder.com/acm/contest/554/H
题解：欧拉筛
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v,a,b;
int ans,cnt,flag,temp,sum;
int pre[N];
bool prime[N];
int d[N];
int num[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
prime[0]=prime[1]=1;
d[1]=1;
for(int i=2;i<N;i++){
if(prime[i]==0){
pre[++cnt]=i;
d[i]=2;
num[i]=1;
}
for(int j=1;j<=cnt&&i*pre[j]<N;j++){
prime[i*pre[j]]=i;
d[i*pre[j]]=d[i]*d[pre[j]];
num[i*pre[j]]=1;
if(i%pre[j]==0){
num[i*pre[j]]=num[i]+1;
d[i*pre[j]]=d[i]/(num[i*pre[j]])*(num[i*pre[j]]+1);
break;
}
}
//cout<<phi[i]<<endl;
}
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&a,&b);
ans=0;
for(int i=a;i<=b;i++){
if((d[i])%2==0){
ans++;
}
}
cout<<ans<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem I
https://ac.nowcoder.com/acm/contest/554/I
京公网安备 11010502036488号