实训第二次上机（假的）题解

10175101159 edited 5 年，11 月前

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;
}

以下为造数据（背锅）的 zerol 的题解：

A:

模拟题意即可。

B:

字符串排序。二维数组会爆内存（题目限制的是字符串总长，所以可能有一个字符串很长，其它的很短），于是只能拿到 85 分，解决方案如下：

C:

高精度，真的无聊，对吧？

D:

数据点 3 中有一组 $2^{60}$ 超出数据范围，实在是对不起大家。

如果会使用 pow 函数并对结果加以验证的话（注意不要爆 long long），很容易做出这题。
当然也可以质因数分解，对指数取最大公因数，但是代码上过于复杂（有兴趣可以看我的代码）。

E:

简单 dp。（第一个点可以用暴搜过。）
$dp[i][j]$ 表示在前 $i$ 个字母中插入加减号后的结果模 $2\times 3 \times 5 \times 7$ 下恰好是 $j$ 的方案数。

上一份 ultmaster 的代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

const int MOD = 1e9 + 7;
const int L = 210;
const int N = 1e3 + 10;
int dp[N][N];
char s[N];

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> s;
        int n = strlen(s);
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int pos = 0; pos < L; ++pos) {
                int tmp = 0;
                for (int j = i + 1; j <= n; ++j) {
                    tmp = (tmp * 10 + s[j - 1] - '0') % L;
                    (dp[j][(pos + tmp) % L] += dp[i][pos]) %= MOD;
                    (dp[j][(pos + L - tmp) % L] += dp[i][pos]) %= MOD;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < L; ++i)
            if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
                (ans += dp[n][i]) %= MOD;
        cout << 1LL * ans * ((MOD + 1) / 2) % MOD << endl;
    }
}

题外话：

E 题本来答案要高精度，但由于已经有一道高精度了，所以删掉了 E 的高精度部分，结果没人过。

Past Versions

Comments

ultmaster
5 年，10 月前

突然意识到我好像一不小心求了个逆元。（其实不应该搞这么不友好的操作的）

回复
10175101159
5 年，10 月前

QAQ

回复
Master X
5 年，10 月前

太强大了

回复
一剑无痕雪满山
5 年，11 月前

去食堂还行哈哈哈哈哈哈好可爱

回复
10175101159
5 年，11 月前

QwQ

回复
Saitama
5 年，11 月前

这样写第一题会快一些

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long LL;

LL gcd(LL a, LL b)
{
    if(a < b)
        return gcd(b, a);
    else
        return a % b == 0 ? b : gcd(b, a % b);
}

void solve(LL n)
{
    LL sum = 0;
    LL tmp = n / 2;
    for(LL i = 2; i <= tmp; i++)
    {
        LL tt = n;
        while(tt)
        {
            sum += tt % i;
            tt /= i;
        }
    }
    sum += (2 + 2 + (n - 1 - n / 2 - 1)) * (n - 1 - n / 2) / 2;
    LL x = gcd(sum, n - 2);
    printf("%lld/%lld\n", sum / x, (n - 2) / x);
}

int main()
{
    LL T;
    cin >> T;
    for(LL i = 0; i < T; i++)
    {
        LL n;
        cin >> n;
        solve(n);
    }
    return 0;
}
回复
10175101159
5 年，11 月前

⊙﹏⊙%

回复
10175101158
5 年，11 月前

膜大佬 嘤嘤嘤

回复
10175101159
5 年，11 月前

O_o

回复
Kevin_K
5 年，11 月前

月莫大佬。

回复
10175101159
5 年，11 月前

qaq并不是

回复
10175101109
5 年，11 月前

好嘛，题解都看不懂。。。

回复
10175101159
5 年，11 月前

$dp[i][j]$这才是E的标准解法（不要像我这样瞎写）
手动@zerol：貌似Contests里没有放到Problems的题目非管理员只能看自己的代码（看不了你的TuT）

回复
Kevin_K
5 年，11 月前

瞎写+1，感觉写的不是一道题。QwQ

回复

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn