10175101159 edited 6 年,7 月前
This is a past version of blog 实训第二次上机(假的)题解
ps:先写了前四题
pps:E题太可怕了,dp一直写挂,去食堂路上突然意识到了什么,回来继续WA,最后突然想到模出负数的bug了
$A$ 小明生日进制数位和均值
$Note:$
数据量不大,直接模拟
注意会爆$int$,$long long$大法好
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n,up,dn,tmp;
ll i;
ll cal(ll num,ll base)
{
ll ret=0;
while(num){
ret+=num%base;
num/=base;
}
return ret;
}
int main()
{
cin>>T;
while(T--){
cin>>n;
up=0;
for(i=2;i<n;++i)up+=cal(n,i);
dn=n-2;
tmp=__gcd(up,dn);
cout<<up/tmp<<'/'<<dn/tmp<<endl;
}
return 0;
}
$B$ 邮件地址排序
$Note:$
结构体排序
#include<bits/stdc++.h>
using namespace std;
int n;
char c;
string tmp;
struct data{
string s,t;
}a[1000000];
int i;
bool cmp(data a,data b)
{
if(a.t!=b.t)return a.t<b.t;
return a.s>b.s;
}
int main()
{
cin>>n;
getchar();
for(i=0;i<n;++i){
while(c=getchar()){
if(c=='@')break;
else tmp+=c;
}
a[i].s=tmp;
tmp="";
while(c=getchar()){
if(c=='\n'||c==EOF)break;
else tmp+=c;
}
a[i].t=tmp;
tmp="";
}
sort(a,a+n,cmp);
for(i=0;i<n;++i)cout<<a[i].s<<'@'<<a[i].t<<endl;
return 0;
}
$C$ 遥远距离
$Note:$
结构体排序+高精度加减
这时候$C++$的$string$的优势就体现出来了
没用模板,手打的高精度,有点糙,凑合着用
#include<bits/stdc++.h>
using namespace std;
int n,tmp;
struct data{
string s;
bool flag;
int num;
}a[50];
char b[126],c[126],d[126];
int i,j;
bool cmp(data a,data b)
{
if(a.flag!=b.flag)return a.flag<b.flag;
if(a.flag){
if(a.num!=b.num)return a.num<b.num;
return a.s<b.s;
}
if(a.num!=b.num)return a.num>b.num;
return a.s>b.s;
}
int main()
{
cin>>n;
for(i=0;i<n;++i){
cin>>a[i].s;
a[i].num=a[i].s.length();
if(a[i].s[0]=='-'){
a[i].flag=1;
a[i].s=a[i].s.substr(1,a[i].num-1);
--a[i].num;
}
}
sort(a,a+n,cmp);
for(i=0;i<126;++i)b[i]=c[i]=d[i]='0';
for(i=125,j=a[0].num-1;j>=0;--j)b[i--]=a[0].s[j];
for(i=125,j=a[n-1].num-1;j>=0;--j)c[i--]=a[n-1].s[j];
if(a[0].flag!=a[n-1].flag){
if(a[0].s=="0"&&a[n-1].s=="0"){
cout<<0;
return 0;
}
bool cf=0;
for(i=125;i>=0;--i){
tmp=b[i]+c[i]-2*'0'+cf;
if(tmp>9)d[i]=(char)(tmp-10+'0'),cf=1;
else d[i]=char(tmp+'0'),cf=0;
}
for(i=0;;++i)if(d[i]!='0')break;
for(j=i;j<126;++j)cout<<d[j];
}
else if(a[0].flag){
if(a[0].s==a[n-1].s){
cout<<0;
return 0;
}
bool cf=0;
for(i=125;i>=0;--i){
tmp=c[i]-b[i]-cf;
if(tmp<0)d[i]=(char)(tmp+10+'0'),cf=1;
else d[i]=char(tmp+'0'),cf=0;
}
for(i=0;;++i)if(d[i]!='0')break;
for(j=i;j<126;++j)cout<<d[j];
}
else{
if(a[0].s==a[n-1].s){
cout<<0;
return 0;
}
bool cf=0;
for(i=125;i>=0;--i){
tmp=b[i]-c[i]-cf;
if(tmp<0)d[i]=(char)(tmp+10+'0'),cf=1;
else d[i]=char(tmp+'0'),cf=0;
}
for(i=0;;++i)if(d[i]!='0')break;
for(j=i;j<126;++j)cout<<d[j];
}
return 0;
}
$D$ 幂次转换
$Note:$
第一眼看预处理质因数,但看到数据范围就怂了
后来想想$2^{64}>10^{18}$(要多刷题积累这种常见的数据大小)
所以直接遍历$base=2,3,…,64$,判断开$base$次根号是不是整数
这样时间复杂度就大大降低了,然后随便瞎写写都不会$TLE$
方法很多,二分查找或者利用类似判断是不是平方数的办法都可以
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int T;
ll n;
bool jdg;
void cal(ll n,ll i)
{
if(n<2)return;
ll tmp=pow((ld)n,(ld)1.0/i)+0.5;
ll rst=1;
for(int j=0;j<i;++j)rst*=tmp;
if(rst==n)cout<<'='<<tmp<<'^'<<i,jdg=0;
}
int main()
{
cin>>T;
while(T--){
cin>>n;
cout<<n;
jdg=1;
for(ll i=2;i<64;++i)cal(n,i);
if(jdg)cout<<" is powerless.";
cout<<endl;
}
return 0;
}
$E$ 变换种类数
$Note:$
首先有一点,判断一个数能否被7整除,可以从低位到高位,按权值$1,3,2,6,4,5$循环累加,判断最终结果能否被7整除
$Reference$:https://blog.csdn.net/paneyjiang/article/details/6722475
想了想,这种方法可以类比到其他任何模数,只要预处理$10^{i}modp,0\le i\le p-1$即可(新知识$get$√)
然后可以用$dp[i][j][m2][m3][m5][m7]$递推
$j=0$表示前$i$位,第$i$位前加$+$得到的结果模$2$同余$m2$,模$3$同余$m3$,模$5$同余$m5$,模$7$同余$m7$的方案数
$j=1$表示前$i$位,第$i$位前加$-$得到的结果模$2$同余$m2$,模$3$同余$m3$,模$5$同余$m5$,模$7$同余$m7$的方案数
$j=2$表示前$i$位,第$i$位前不填得到的结果模$2$同余$m2$,模$3$同余$m3$,模$5$同余$m5$,模$7$同余$m7$的方案数
状态转移方程:
$j=0,1$时,$dp[i][j][m2][m3][m5][m7]$仅由$dp[i-1][0/1/2][m2][m3][m5][m7]$决定,此处略去
$j=2$时,遍历$0,1,2,\cdots,i-1$作最后一个符号的位置,判断结果累加,注意还有一种是整串不添加一个符号单独判断
为方便起见,这里写了$int cal(int lft,int rgt,int mod)$计算原串第$lft$位到第$rgt$位表示的整数模$p$的结果
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll P=1e9+7;
int T,len,tmp;
string s;
ll dp[105][3][2][3][5][7],tdp[2][3][5][7];
int i,j;
int cal(int lft,int rgt,int mod)
{
int i,tmp=0;
if(mod==2)return (s[rgt]-'0')%2;
if(mod==3){
for(i=lft;i<=rgt;++i)tmp+=s[i]-'0';
return tmp%3;
}
if(mod==5)return (s[rgt]-'0')%5;
int a[6]={1,3,2,6,4,5};
for(i=rgt;i>=lft;--i)tmp+=a[(rgt-i)%6]*(s[i]-'0');
return tmp%7;
}
int main()
{
cin>>T;
while(T--){
cin>>s;
len=s.length();
memset(dp,0,sizeof(dp));
tmp=s[0]-'0';
++dp[0][0][tmp%2][tmp%3][tmp%5][tmp%7];
for(i=1;i<len;++i){
//第i位前空有填
tmp=s[i]-'0';
int m2=tmp%2,m3=tmp%3,m5=tmp%5,m7=tmp%7;
int p,q,r,s;
//+
memset(tdp,0,sizeof(tdp));
for(p=0;p<2;++p)for(q=0;q<3;++q)
for(r=0;r<5;++r)for(s=0;s<7;++s){
tdp[(p+m2)%2][(q+m3)%3][(r+m5)%5][(s+m7)%7]
+=dp[i-1][0][p][q][r][s]
+dp[i-1][1][p][q][r][s]
+dp[i-1][2][p][q][r][s];
}
for(p=0;p<2;++p)for(q=0;q<3;++q)
for(r=0;r<5;++r)for(s=0;s<7;++s)
dp[i][0][p][q][r][s]=tdp[p][q][r][s]%P;
//-
memset(tdp,0,sizeof(tdp));
for(p=0;p<2;++p)for(q=0;q<3;++q)
for(r=0;r<5;++r)for(s=0;s<7;++s){
tdp[(p-m2+2)%2][(q-m3+3)%3][(r-m5+5)%5][(s-m7+7)%7]
+=dp[i-1][0][p][q][r][s]
+dp[i-1][1][p][q][r][s]
+dp[i-1][2][p][q][r][s];
}
for(p=0;p<2;++p)for(q=0;q<3;++q)
for(r=0;r<5;++r)for(s=0;s<7;++s)
dp[i][1][p][q][r][s]=tdp[p][q][r][s]%P;
//第i位前空不填
memset(tdp,0,sizeof(tdp));
for(j=0;j<i-1;++j){
m2=cal(j+1,i,2),m3=cal(j+1,i,3),m5=cal(j+1,i,5),m7=cal(j+1,i,7);
for(p=0;p<2;++p)for(q=0;q<3;++q)
for(r=0;r<5;++r)for(s=0;s<7;++s){
tdp[(p+m2)%2][(q+m3)%3][(r+m5)%5][(s+m7)%7]
+=dp[j][0][p][q][r][s]
+dp[j][1][p][q][r][s]
+dp[j][2][p][q][r][s];
tdp[(p-m2+2)%2][(q-m3+3)%3][(r-m5+5)%5][(s-m7+7)%7]
+=dp[j][0][p][q][r][s]
+dp[j][1][p][q][r][s]
+dp[j][2][p][q][r][s];
}
}
m2=cal(0,i,2),m3=cal(0,i,3),m5=cal(0,i,5),m7=cal(0,i,7);
++tdp[m2][m3][m5][m7];
for(p=0;p<2;++p)for(q=0;q<3;++q)
for(r=0;r<5;++r)for(s=0;s<7;++s)
dp[i][2][p][q][r][s]=tdp[p][q][r][s]%P;
}
ll rst=0;
int p,q,r,s;
for(p=0;p<2;++p)for(q=0;q<3;++q)
for(r=0;r<5;++r)for(s=0;s<7;++s){
if(p&&q&&r&&s)continue;
rst=(rst+dp[len-1][0][p][q][r][s])%P;
rst=(rst+dp[len-1][1][p][q][r][s])%P;
rst=(rst+dp[len-1][2][p][q][r][s])%P;
}
cout<<rst<<endl;
}
return 0;
}