前面的碎碎念
菜鸡被碾压的一场比赛，就会一题。
比赛传送门
A、相反数
思路：
签到题，直接枚举每一位， (n)能过，我写这一题的时候居然慌了。
Code：
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
char s[20];
int ans=0;
int main() {
js;
cin>>s;
for(int i=0,j=strlen(s)-1;s[i];++i,--j) {
ans=ans*10+s[i]-'0'+s[j]-'0';
}
cout<<ans<<endl;
}B、Music Problem
题意转换：
T组数据，每组数据n个数，取任意个数的和取模，问会不会有取模为0的和，这像极了牛客OI周赛15-普及组的B题，这道题是01背包，而那个是多重背包。刚开始刘大佬说的时候我没想到，现在看一下就明白了。
传送戳我
思路：
总的共有3600种结果，每输入一个数就记录此时全部的和，然后维护dp[i]：dp[i]=1表示存在一种组合的和为i。
复杂度 (3600*n)。
Code：
#include<bits/stdc++.h>
using namespace std;
int dp[3600],a[3600],cnt;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
int n,t,x;
int main() {
t=read();
while(t--) {
memset(dp,0,sizeof(dp));
n=read();
int i;
for(i=1;i<=n&&!dp[0];++i) {
x=read()%3600;
cnt=0;
for(int j=1;j<3600;++j) if(dp[j]) a[cnt++]=(j+x)%3600;
for(int j=0;j<cnt;++j) dp[a[j]]=1;
dp[x]=1;
}
while(i++<=n) x=read();
if(dp[0]) puts("YES");
else puts("NO");
}
}
C、完全平方数
注意：0也是完全平方数。
1e7，小白试了试打表，才31623个平方数，就决定用打表的方式写了，求出左右边界的时候脑抽了不知道是r-l+1还是r-l，是有点蠢，想了很久，结果提交后超出代码的长度了。然后按钟涛大佬的说法可以二分，我写不出来
，然后就一直没a了，真的就是钟涛大佬说的那样，打表打傻了，打表真的有毒。
思路：
不能外部打表，才3e4个数据内部打表就可以了，我居然没想到。然后巧用两个STL函数upper_bound(a,a+tot,r)-a和lower_bound(a,a+tot,l)-a，分别返回第一个大于右边界和第一个小于等于左边界的平方数的下标，如果没找到是返回a+tot，复杂度盲猜 (log n)。
Code：
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int a[31625];
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
void print(int x){
if(x>=10) print(x/10);
putchar(x%10+'0');
}
int t,l,r,tot;
int main(){
for(int i=0;i*i<=1000000000;++i) {
a[tot++]=i*i;
}
t=read();
while(t--) {
l=read(),r=read();
r=upper_bound(a,a+tot,r)-a;
l=lower_bound(a,a+tot,l)-a;
print(r-l),puts("");
}
}D、小H和游戏
思路：
f[i][k]：表示结点i距离爆炸中心k个单位被炸的次数。
所以我们不用每次都维护每个结点的f数组，只要维护该结点的父结点和父结点的父结点就可以了，输出结果时就往上找到父结点和父结点的父结点。
每个结点爆炸时他的父亲和爷爷和儿子还有孙子都会被炸，所以f[fa[i]][1]、f[fa[fa[i]][2]都要加一次。儿子和孙子的结果只要再访问父亲和爷爷就可以了。
用链式向前星存图，然后dfs构建树，复杂度盲猜 (n),但是查询是
(1)。
Code：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int f[750005][3],head[750005],Next[750005<<1],to[750005<<1],fa[750005],tot;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
void print(int x){
if(x>=10) print(x/10);
putchar(x%10+'0');
}
inline void add(int x,int y) {
to[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int f) {
fa[x]=f;
for(int i=head[x];i;i=Next[i]) {
if(to[i]==f) continue;
dfs(to[i],x);
}
}
int n,x,y,Q,ans;
int main() {
n=read(),Q=read();
for(int i=2;i<=n;++i) {
x=read(),y=read();
add(x,y);
add(y,x);
}
dfs(1,0);
while(Q--) {
x=read(),ans=0;
++f[x][0];
if(fa[x]) {
++f[fa[x]][1];
ans=f[fa[x]][0]+f[fa[x]][1]-f[x][0];
}
if(fa[fa[x]]) {
++f[fa[fa[x]]][2];
ans+=f[fa[fa[x]]][0];
}
ans+=f[x][0]+f[x][1]+f[x][2];
print(ans),puts("");
}
return 0;
}E、水题(water)
前导知识和推导：
n!的质因子数如果直接暴力去搜复杂度非常大，可以 (long n)去求。就是cnt+=n/q,n/=q（q为质因数）。这样一直下去直到n为0，比如25!，质因数为2，25/2=12，表示12个数是可以乘2得到：12，22，32，42...
25/4同上。
会发现2=12刚好就一个2，4=22=14有两个2，8=222=24=28，24被计算2次，1*8计算了一次，刚好是8质因数2的总数。
n皇后可以直接打表，最大才13，我是套用江大佬的模板算的。
思路：
题目的f[i]是斐波那契数列。
矩阵快速幂求斐波那契，最多到第89项就可以了，再判断x是不是斐波那契。是的话求出n!质因数pi的x次幂是m质因数pi的k次幂的多少倍中的最小值，否则直接输出n皇后的方案数。
Code：
（很多部分都是板子所以这么长）
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
struct node {
ll matrix[2][2];//结构体中的矩阵
node() {
memset(matrix,0,sizeof(matrix));
}//构造函数，定义一个结构体时自动调用
void one() {
matrix[0][0]=1;
matrix[1][1]=1;
}//单位矩阵
node operator*(node other) {
node ans;//记录乘积
for(int i=0; i<2; i++)
for(int j=0; j<2; j++)
for(int k=0; k<2; k++)
ans.matrix[i][j] += matrix[i][k]*other.matrix[k][j];
return ans;
}//定义了结构体后就会有这个性质 operator是是对*的重载
};
/*
* 相当于p1的一个成员函数
p1*p2相当于对象p1调用函数“operator*”，把对象p2作为一个参数传递给该函数，从而实现了两个对象的相乘。
*/
node power(node a,ll b) {
node res;
res.one();//单位矩阵
while(b) {
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}//快速幂求a的b次方
int QUEEN[107];
int N, Num = 0;
void SetQueen(ll Row, ll Column, ll LeftSlash, ll RightSlash) {
ll available = ((1 << N) - 1) & ~(Column | LeftSlash | RightSlash);
while (available) {
ll p = available & -available;
available ^= p;
QUEEN[Row] = (int)(log2(p)) + 1;
if (Row == N - 1) {
++Num;
//for (int i = 0; i < N; ++i) cout << QUEEN[i] << " ";
//cout << endl;
}
else
SetQueen(Row + 1, Column | p, (LeftSlash | p) >> 1,
(RightSlash | p) << 1);
}
}
ll x;
int m,flag;
int main() {
node temp,ans1;//初始矩阵
temp.matrix[0][0]=1; //a[2]
temp.matrix[0][1]=1; //a[1]
temp.matrix[1][0]=1;
temp.matrix[1][1]=0;
js;
cin>>x>>m;
for(int i=2;i<=88;++i) {
ans1 = power(temp,i-1);
if(x==ans1.matrix[0][0]) {
flag=1;
break;
}
}
//cout<<x<<" "<<ans1.matrix[0][0]<<endl;
if(flag) {
ll ans=0x3f3f3f3f3f3f3f3f,sm1,sm2;
for(int i=2;i<=100;++i) {
if(m%i) continue;
sm1=sm2=0;
while(m%i==0) m/=i,++sm1;
ll sum=x;
while(sum) sm2+=sum/i,sum/=i;
ans=min(ans,sm2/sm1);
}
cout<<ans<<endl;
}
else {
N = x % min(13, m) + 1;
SetQueen(0, 0, 0, 0);
cout<<Num<<endl;
}
}
京公网安备 11010502036488号