A
看到要去前导0，直接字符串模拟了，倒着的时候从第一个不为0的数字开始计算这个数字大小，加上原来数字即可
#include
using namespace std;
typedef long long ll;
int main(){
char s[10];
cin>>s;
int sum=0;
for(int i=0;i<strlen(s);i++) sum=sum*10+s[i]-'0';
int flag=0;
int a=0;
for(int i=strlen(s)-1;i>=0;i--){
if(s[i]!='0'){
flag=1;
}
if(flag){
a=a*10+s[i]-'0';
}
}
cout<<sum+a<<endl;
return 0;
}B
问题：将一些数字取任意个相加能不能拼凑出3600的倍数，就是背包有无解的问题。
两种做法。
第一种：直接bitset优化.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
bitset<3600> q;
for(int i=1;i<=n;i++){
int x;cin>>x;
x%=3600;
//右端第一部分是说已经有的基础上再加一个x， 第二部分是溢出3600的部分取余
q |= (q << x) | (q >> (3600-x));
q[x]=1;//将x添加上去
}
if(q[0]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
感谢评论区hx073269大哥指正 第二种是个假算法 复杂度爆掉了 应该是数据水了。当然有兴趣的可以看下？(狗头
第二种，想一下，如果n≥3600一定有解，为什么？证明如下：
设
如果对于n个sum取余3600后，余数在0到3599之间都有位置，显然有解。
如果在0~3599有的位置没有，说明至少存在两个位置的sum%3600后的值一样，那么区间的一段就是3600的倍数。得证。
所以n≥3600 直接输出YES
否则跑个背包判断有无解。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
if(n>=3600) cout<<"YES"<<endl;
else
{
vector<vector<int>> dp(n+1,vector<int>(3600));
dp[0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<3600;j++){
if(dp[i][j]){
dp[i+1][j]+=dp[i][j];
dp[i+1][(j+a[i+1])%3600]+=dp[i][j];
}
}
}
if(dp[n][0]>1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
return 0;
}C
判断l到r之间有多少个完全平方数，然后判断端点l是不是完全平方数即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;
cin>>n;
while(n--)
{
ll l,r;
cin>>l>>r;
ll s1=sqrt(l)+0.000001,s2=sqrt(r)+0.000001;
ll num=s2-s1;
if(s1*s1==l) num++;
cout<<num<<endl;
}
return 0;
}D
考虑开一个二维数组cnt[n][3]
cnt[i][0]表示i受到的波及次数，
cnt[i][1]表示i对儿子节点的波及次数
cnt[i][2]表示i对孙子节点的波及次数
那么对于每次询问，i肯定对i的儿子和孙子造成了波及，所以cnt[i][1]++,cnt[i][2]++
那么往上考虑，i也对他父亲和爷爷造成了波及所有 cnt[f[i]][0]++,cnt[f[f[i]][0]++
还有一点要注意，i本身和i的同父亲的兄弟也会收到波及，那么这里我们要怎么加呢？直接加到i的父亲节点对儿子节点的波及即可，也就是cnt[f[i]][1]++，这样就同时加入了i本身和他兄弟受到的影响
那么对于每个点i，受到的波及次数就是cnt[1][0]+cnt[f[i]][1]+cnt[f[f[i]][2]
即自身收到子节点的波及次数+父亲对自己的波及次数+爷爷对自己的波及次数
所以dfs求出每个点的父亲后按照上述过程模拟即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1<<20;
vector<int>e[maxn];
int cnt[maxn][3];///自己、儿子、孙子
int f[maxn];
void dfs(int x,int fa){
f[x]=fa;
for(auto it:e[x]){
if(it==fa) continue;
dfs(it,x);
}
}
int main(){
ios::sync_with_stdio(0);
int n,m;cin>>n>>m;
for(int i=1;i<n;i++){
int a,b;cin>>a>>b;
e[a].push_back(b);
e[b].push_back(a);
}
dfs(1,0);
f[0]=maxn-1;
while(m--){
int a;cin>>a;
cnt[a][1]++,cnt[a][2]++;
cnt[f[a]][1]++,cnt[f[a]][0]++;
cnt[f[f[a]]][0]++;
cout<<cnt[a][0]+cnt[f[a]][1]+cnt[f[f[a]]][2]<<endl;
}
return 0;
}
E
E题中的式子其实就是斐波那契数列的几何意义
其实就是问n是不是斐波那契数，是的话输出它的阶乘在m进制下有多少个0，质因数分解完事。
不是的话，就是问1~13皇后有多少种分布方式。
懒得写了。。（其实是太菜了） 还是补了一下
枚举m的质因子i，然后去看x!中有多少个i，我们只需要取最小即可。13皇后？表打出来即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[]={-1, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712};
ll inf=1e18;
ll f[5005];
int main(){
int cnt;
f[1]=f[2]=1;
for(cnt=3;;cnt++){
f[cnt]=f[cnt-1]+f[cnt-2];
if(f[cnt]>=inf) break;
}
ll x,m;cin>>x>>m;
int flag=0;
for(int i=1;i<=cnt;i++) {
if(f[i]==x){
flag=1;
break;
}
}
if(flag){
ll ans=1e18;
for(int i=2;i*i<=m;i++){
if(m%i==0){
ll num=0;
while(m%i==0) m/=i,num++;
ll num1=0;
ll y=x;
while(y) num1+=y/i,y/=i;
ans=min(ans,num1/num);
}
}
if(m!=1) {
ll num=0;
while(x) num+=x/m,x/=m;
ans=min(ans,num);
}
cout<<ans<<endl;
}
else cout<<a[x%min(13ll,m)+1];
return 0;
}
京公网安备 11010502036488号