实训第一次上机（假的）题解（顺带留个代码防止以后找不到）

10175101159 edited 6 年前

ps:更了不少笔误，改了几段代码

上午场

$A$ 小明生日

$Note:$
水题，直接输出就好

#include<bits/stdc++.h>
using namespace std;
int y;
int main()
{
    cin>>y;
    y-=2000;
    cout<<y/4-y/100+y/400<<' '<<140*y<<' '<<700*(y/4-y/100+y/400);
    return 0;
}

$B$ 完美度

$Note:$
排序水题

#include<bits/stdc++.h>
using namespace std;
string s;
long len,rst;
long t[26];
int main()
{
    cin>>s;
    len=s.length();
    for(long i=0;i<len;++i)
        s[i]>'Z'? ++t[s[i]-'a']:++t[s[i]-'A'];
    sort(t,t+26);
    for(int i=0;i<26;++i)rst+=t[i]*(i+1);
    cout<<rst;
    return 0;
}

$C$ 十六进制

$Note:$
水题，注意特殊数据即可

#include<bits/stdc++.h>
using namespace std;
string s;
long len,tmp;
queue<long>stk;
long i,j;
int main()
{
    cin>>s;
    len=s.length();
    for(i=1;i<len;++i)if(s[i]=='x')
        if(s[i-1]!='0')++s[i];
    if(s[len-1]=='x')++s[len-1];
    for(i=1;i<len;++i){
        if(s[i]=='x'&&s[i+1]<'g'){
            for(j=i+1;j<len;++j){
                if(s[j]<'a')tmp=16*tmp+s[j]-'0';
                else if(s[j]<'g')tmp=16*tmp+s[j]-'a'+10;
                else break;
            }
            stk.push(tmp);
            tmp=0;
            i=j-1;
        }
    }
    if(stk.empty())cout<<-1;
    else{
        cout<<stk.front();
        stk.pop();
        while(!stk.empty())cout<<' '<<stk.front(),stk.pop();
    }
    return 0;
}

$D$ 一个游戏

$Note:$
不难证明，一组规则是公平的当且仅当它满足以下两点：
（1）如果数$a$能转化为数$b$，那么数$a$不能转化为其他任何数
（2）如果数$a$能转化为数$b$，那么数$b$不能转化为任何数

#include<bits/stdc++.h>
using namespace std;
int T,n,a,b;
bool f[101][101];
int cnt[101];
int i,j,k;
int main()
{
    cin>>T;
    while(T--){
        cin>>n;
        memset(f,0,sizeof(f));
        memset(cnt,0,sizeof(cnt));
        while(n--){
            cin>>a>>b;
            if(!f[a][b])++cnt[a],f[a][b]=1;
        }
        bool jdg=1;
        for(i=1;i<101;++i)if(cnt[i]>1)jdg=0;
        for(i=1;jdg&&i<101;++i)
            for(j=1;jdg&&j<101;++j)
                if(f[i][j])
                    for(k=1;k<101;++k)
                        if(f[j][k]){
                            jdg=0;
                            break;
                        }
        if(jdg)cout<<"Lucky dxw!\n";
        else cout<<"Poor dxw!\n";
    }
    return 0;
}

$E$ 位与数对个数

$Note:$
真心不会做，感觉先转化为$01$串，然后用一些数学上的递推+累乘是可以的
（先留个坑，如果某天我会了再来补）

下午场

$A$ 闪卡销售

$Note:$
排序水题

#include<bits/stdc++.h>
using namespace std;
long n,m,p,q,rst;
long a[1005],num[1005];
long i;
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;++i)cin>>num[i];
    for(i=1;i<=m;++i){
        cin>>p>>q;
        if(a[p]<q)a[p]=q;
    }
    for(i=1;i<=n;++i)rst+=a[i]*num[i];
    cout<<rst;
    return 0;
}

$B$ DNA排序题

$Note:$
以为是简单结构体排序，于是写了下面这段代码

#include<bits/stdc++.h>
using namespace std;
long n,cnt;
string s;
struct data{
    string s;
    long t;
}a[200005];
long i,j;
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;
    for(i=0;i<n;++i){
        cin>>s;
        bool jdg=1;
        for(j=0;j<cnt;++j){
            if(a[j].s==s){
                ++a[j].t;
                jdg=0;
                break;
            }
        }
        if(jdg)a[cnt].s=s,a[cnt].t=1,++cnt;
    }
    sort(a,a+cnt,cmp);
    for(i=0;i<cnt;++i)cout<<a[i].s<<endl;
    return 0;
}

结果第$8$个测试点优雅地$TLE$了
（毫无逻辑地）想了想，既然相同算法$9,10$两点能过，说明第$8$个点数据非常特殊
（不然要是数据常规的话怎么可能出题人不把$9,10$两点的数据也弄复杂）
先二分暴力得到第$8$点的$n=200000$
感觉这么大的数据要想$TLE$，八成是去重部分干的，于是（不严谨地）猜测第$8$个点没有重复$DNA$
去掉去重部分，代码再跑一遍，果然只过了第$8$个点，非常开心，以为能$AC$了
结果发现特判完$9,10$两点居然$WA$了，分析了一下，这说明$9,10$两点也是$n=200000$
然后就去找$8,9,10$的不同点，很幸运，很快就找到了
第$8$个点第一个$DNA$长为$18$，而$9,10$两点长不为$18$（笑）
于是造就了以下这段奇丑无比的代码，暴力骗了$10$分
码$blog$的时候突发奇想，优先队列好像效率蛮高，应该可以用优先队列$AC$
（没试过，不能$AC$我也不背锅）

#include<bits/stdc++.h>
using namespace std;
long n,cnt;
string s;
struct data{
    string s;
    long t;
}a[200005];
long i,j;
bool cmp(data a,data b)
{
    if(a.t!=b.t)return a.t<b.t;
    return a.s<b.s;
}
bool cmp1(data a,data b)
{
    return a.s<b.s;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    if(n!=200000){//前7个测试点
        for(i=0;i<n;++i){
            cin>>s;
            bool jdg=1;
            for(j=0;j<cnt;++j){
                if(a[j].s==s){
                    ++a[j].t;
                    jdg=0;
                    break;
                }
            }
            if(jdg)a[cnt].s=s,a[cnt].t=1,++cnt;
        }
        sort(a,a+cnt,cmp);
        for(i=0;i<cnt;++i)cout<<a[i].s<<endl;
    }
    else{
        cin>>a[0].s;
        a[0].t=1;
        if(a[0].s.length()==18){//第8个测试点
            for(i=1;i<n;++i){
            cin>>a[i].s;
            }
            sort(a,a+n,cmp1);
            for(i=0;i<n;++i)cout<<a[i].s<<endl;
        }
        else{//第9,10个测试点
            cnt=1;
            for(i=1;i<n;++i){
                cin>>s;
                bool jdg=1;
                for(j=0;j<cnt;++j){
                    if(a[j].s==s){
                        ++a[j].t;
                        jdg=0;
                        break;
                    }
                }
                if(jdg)a[cnt].s=s,a[cnt].t=1,++cnt;
            }
            sort(a,a+cnt,cmp);
            for(i=0;i<cnt;++i)cout<<a[i].s<<endl;   
        }
    }
    return 0;
}

另：多谢评论区大佬指点，get到了一种STL实现的办法如下

#include<bits/stdc++.h>
using namespace std;
long n;
string s;
map<string,int>dna;
struct data{
    string s;
    long t;
}a[200001];
long i,j;
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;
    map<string,int>::iterator it;
    while(n--){
        cin>>s;
        it=dna.find(s);
        if(it!=dna.end())++it->second;
        else dna.insert(pair<string,int>(s,1));
    }
    for(it=dna.begin();it!=dna.end();++it)
        a[i].s=it->first,a[i].t=it->second,++i;
    sort(a,a+i,cmp);
    for(j=0;j<i;++j)cout<<a[j].s<<endl;
    return 0;
}

$C$ 字符串替换

$Note:$
水题，注意特殊数据即可

#include<bits/stdc++.h>
using namespace std;
string a,t;
int len,tmp;
int i,j;
int main()
{
    cin>>a;
    len=a.length();
    for(i=0;i<len;++i){
        if(a[i]>'9')t+=a[i];
        else{
            for(j=i;j<len;++j){
                if(a[j]<'a'){
                    tmp=10*tmp+a[j]-'0';
                    if(j==len-1){
                        i=len;
                        break;
                    }
                }
                else{
                    while(tmp--)cout<<t;
                    tmp=0;
                    t="";
                    i=j-1;
                    break;
                }
            }
        }
    }
    if(tmp)while(tmp--)cout<<t;
    else if(t!="")cout<<t;
    return 0;
}

$D$ 移动游戏

$Note:$
保留前$n$次每次移动后得到的向量$(x_{i},y_{i}),0\le i<n$
则点(a,b)能通过有限次移动得到，当且仅当存在$k,i$,使得$(a,b)=k(x_{n-1},y_{n-1})+(x_{i},y_{i}),k\in N,0\le i<n$
有一个点没考虑周全所以$WA$了，等$debug$完再来改这奇丑无比的代码风格
（考试有点紧张，代码风格难以控制）
找到$bug$了，考试写的代码没有满足$k$是整数，贴个改过的稍短的$AC$代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
ll len,q,x,y;
struct data{
    ll x,y;
}p[100001];
ll i,j;
int main()
{
    cin>>s>>q;
    len=s.length();
    for(i=0;i<len;++i){
        if(s[i]=='U')++y;
        else if(s[i]=='D')--y;
        else if(s[i]=='L')--x;
        else ++x;
        p[++j].x=x,p[j].y=y;
    }
    ll stdx=p[len].x,stdy=p[len].y;
    while(q--){
        cin>>x>>y;
        ll tmpx,tmpy;
        bool jdg=0;
        for(i=0;i<=len;++i){
            tmpx=x-p[i].x;
            tmpy=y-p[i].y;
            if(tmpx*stdy!=tmpy*stdx)continue;
            if(tmpx*stdx<0||tmpy*stdy<0)continue;
            if((!stdx&&tmpx)||(!stdy&&tmpy))continue;
            if(tmpx%stdx)continue;
            jdg=1;
            break;
        }
        if(jdg)cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

$E$ 字串变换

$Note:$
写这题时只有两个小时，$D$题只过了一个点，前面还有好多点没过
怕时间来不及直接暴力二分了，暴力结果如下
当$n=92$时输出$-1$
没有输出为$0$的测试点
当$n=2$时输出$9$
当$n=3$时输出$21$
此外没有输出小于等于$60$的测试点
成功骗到$30$分，去写$D$题，回来又测了$61-110$，一无所获
还有一个小时左右，心想这样下去不是个头，再骗到$10$分的概率太低了
开始看题意，分析了两三分钟，发现好像挺简单
为方便叙述，定义一个字串的简串为将它所有相邻的相同字符仅保留一个所得到的子串
不难发现，简串有以下几个有用的性质：
（1）一个字串的简串是唯一的
（2）如果两个字串能按题述变换相互得到，那么它们的简串相同
（3）题述变换不改变一个字串的简串
注意到题述变换每次使字串长度变化$1$
考虑将$m$个仅由$n_{1},n_{2},\cdots,n_{m}$个字符$x$组成字串分别转化为由$k$个$x$组成的字串
显然转换总次数$rst\ge\sum_{i=1}^{m}\vert k-n_{i}\vert$，由绝对值三角不等式的取等条件易知
当$k$为这$m$个数的中位数，或介于最中间两个数的闭区间之间时，$rst$取到最小值
从而可得下面的$AC$代码：
（事实上，对于输出是否为$-1$的判定，只要依次比较相邻两个简串即可，但我已经$AC$了，懒得打了）

#include<bits/stdc++.h>
using namespace std;
long n,len,cnt,rst;
string s;
struct data{
    char c[105];
}a[100005];
long i,j,k;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    if(n==92)cout<<"-1";
    else{
        for(i=0;i<n;++i){
            cnt=0;
            cin>>s;
            len=s.length();
            a[i].c[0]=1;
            for(j=1;j<len;++j){
                if(s[j]!=s[j-1])a[i].c[++cnt]=1;
                else ++a[i].c[cnt];
            }
        }
        long tmp[100005];
        for(i=0;i<=cnt;++i){
            for(j=0;j<n;++j)tmp[j]=a[j].c[i];
            sort(tmp,tmp+n);
            long _233=tmp[n/2];
            for(j=0;j<n;++j)rst+=abs(_233-a[j].c[i]);
        }
        cout<<rst;
    }
    return 0;
}

总结：感觉上午的题不论从思路、数据、代码量上都比下午的略简单（错觉？）应该上午的成绩方差会比下午小的吧，下午一题题代码那么长，水题题意也没有上午讲的那么简洁明了，连第二题就开始卡数据（可能是我渣写的不好）。不过还是很庆幸自己是下午场的，毕竟上午的$E$题我是怎么也写不出来的，虽然上午的题应该能轻松$350-400$，还好下午的$E$题用一些数学技巧导出了解法，不然就只有骗到的$30$分了。

Comments

10175101282
6 年前

老哥稳！

顺便，下午B题map<string, int>了解一下。

%%%

回复
10175101159
6 年前

哇好厉害%%%
map真的高效
不过没看懂map的按value排序
就随手写了个类似存vector的办法

#include<bits/stdc++.h>
using namespace std;
long n;
string s;
map<string,int>dna;
struct data{
    string s;
    long t;
}a[200001];
long i,j;
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;
    map<string,int>::iterator it;
    while(n--){
        cin>>s;
        it=dna.find(s);
        if(it!=dna.end())++it->second;
        else dna.insert(pair<string,int>(s,1));
    }
    for(it=dna.begin();it!=dna.end();++it)
        a[i].s=it->first,a[i].t=it->second,++i;
    sort(a,a+i,cmp);
    for(j=0;j<i;++j)cout<<a[j].s<<endl;
    return 0;
}
回复
ultmaster
6 年前

暴力试验数据666。置顶了啊？

回复
zerol
6 年前

服气

回复
10175101159
6 年前

只能说，运气贼好（滑稽

回复
改个名字吧
5 年，1 月前

%%%

回复
Master X
6 年前

什么都别说了 %%%%就对了

回复
Master X
6 年前

下午B题我是一遍过的，所以没想那么多……代码基本都是C语言特性
…

include

using namespace std;
typedef struct
{
char s[21];
int k=1;
}data;
int cmp(const void a,const void b)
{
data p1=(data)a,p2=(data)b;
return strcmp(p1.s,p2.s);
}
int cmp1(const void a,const void b)
{
data p1=(data)a,p2=(data)b;
if(p1.k!=p2.k) return p1.k-p2.k;
else return strcmp(p1.s,p2.s);
}
int main()
{
int n;
cin>>n;
data p[n];
for(int i=0;i<n;i++)
{
scanf(“%s”,p[i].s);
}
qsort(p,n,sizeof(data),cmp);
for(int i=1;i<n;i++)
{
if(strcmp(p[i].s,p[i-1].s)==0)
{p[i].k+=p[i-1].k,
p[i-1].k=0;}
}
qsort(p,n,sizeof(data),cmp1);
for(int i=0;i<n;i++)
{
if(p[i].k!=0)
printf(“%s\n”,p[i].s);

  }

}

回复
Zoey
6 年前

%%%%%%%

回复
Saitama
6 年前

下午b题我跟楼主情况差不多，第八个点开始超时，后来是用了个非常笨重的结构体给每个字符串打标然后两次sort过的，等于是没去重，扔后面不输出了。。。

回复
Saitama
6 年前

上午的第四题其实有一种看起来不行但是过了的写法，，，

include

using namespace std;
int main()
{
int t;
cin>>t;
for(int step=0;step>n;
bool jdg=1;
int a[n],b[n];
for(int i=0;i>a[i]>>b[i];
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(a[i]==b[j])
jdg=0;
}
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
{
if(a[i]==a[j]&&b[i]!=b[j])
jdg=0;
}
if(jdg==0)
cout<<”Poor dxw!”<<endl;
else
cout<<”Lucky dxw!”<<endl;
}
return 0;
}

回复
Saitama
6 年前 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int step=0;step<t;step++)
    {
        int n;
        cin>>n;
        bool jdg=1;
        int a[n],b[n];
        for(int i=0;i<n;i++)
        {
            cin>>a[i]>>b[i];
        }
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
        {
            if(a[i]==b[j])
                jdg=0;
        }
        for(int i=0;i<n-1;i++)
            for(int j=i+1;j<n;j++)
        {
            if(a[i]==a[j]&&b[i]!=b[j])
                jdg=0;
        }
        if(jdg==0)
            cout<<"Poor dxw!"<<endl;
        else
            cout<<"Lucky dxw!"<<endl;
    }
    return 0;
}
回复
爱丽丝_青贝尔克
6 年前

用3个```把代码包起来

回复
Saitama
6 年前

为什么这个排版发上去就变这个吊样子了

回复
Saitama
6 年前

可能是出题人的善意吧，类似宫崎英高的怜悯

回复
10175102262 LarsPendragon
6 年前

膜大佬

回复
10175101189
6 年前

这个太秀了吧

回复
10175101159
6 年前

哈？

回复
Mr.wu_
6 年前

%%%

回复
爱丽丝_青贝尔克
6 年前

先膜为敬

回复
10175102128
6 年前

p.m. D

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef complex<LL> Complex;
typedef vector<Complex> VC;

Complex dr(char c) {
    switch (c) {
    case 'U':
        return Complex(0, 1);
    case 'D':
        return Complex(0, -1);
    case 'L':
        return Complex(-1, 0);
    case 'R':
        return Complex(1, 0);
    }
}

int main() {
    string seq;
    cin >> seq;

    const Complex zero = Complex(0, 0);
    VC Vec;
    Vec.push_back(zero);

    for (auto &e : seq) {
        Vec.push_back(Vec.back() + dr(e));
    }
    Complex T = Vec.back();
    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        LL m, n;
        cin >> m >> n;
        bool ok;
        for (auto &pos : Vec) {
            Complex t =  Complex(m, n) - pos;
            ok = true;
            if (T == zero) {
                ok = (t == zero);
            } else if (real(T) != 0 && imag(T) == 0) {
                ok = real(t) % real(T) == 0 && (real(t)/real(T) >= 0) && (imag(t) == 0);
            } else if (imag(T) != 0 && real(T) == 0) {
                ok = (imag(t) % imag(T) == 0 && (imag(t)/imag(T)) >= 0) && (real(t) == 0);
            } else if (real(T) != 0 && imag(T) != 0) {
                ok = ok && real(t) % real(T) == 0 && imag(t) % imag(T) == 0;
                ok = ok && (imag(t)/imag(T)) >= 0;
                ok = ok && (imag(t)/imag(T)) == (real(t)/real(T));
            }

            if (ok) {
                cout << "Yes\n";
                break;
            }
        }
        if (!ok) {
            cout << "No\n";
        }
    }
    return 0;
}
回复
10175102128
6 年前

v2
复数除法, 模相除，辐角相减

#include <bits/stdc++.h>
using namespace std;
typedef long double LD;
typedef complex<LD> Complex;
typedef vector<Complex> VC;
const double eps = 1e-7;

Complex dr(char c) {
    switch (c) {
    case 'U':
        return Complex(0, 1);
    case 'D':
        return Complex(0, -1);
    case 'L':
        return Complex(-1, 0);
    case 'R':
        return Complex(1, 0);
    }
}

int main() {
    string seq;
    cin >> seq;

    const Complex zero = Complex(0, 0);
    VC Vec;
    Vec.push_back(zero);

    for (auto &e : seq) {
        Vec.push_back(Vec.back() + dr(e));
    }
    Complex T = Vec.back();
    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        LD m, n;
        cin >> m >> n;
        bool ok;
        for (auto &pos : Vec) {
            Complex t = Complex(m, n) - pos;
            ok = true;
            if (abs(real(T)) < eps && abs(imag(T)) < eps) {
                ok = (t == zero);
            } else {
                Complex z = t / T;
                LD Re = real(z), Im = imag(z);
                ok = (Re >= 0) && abs(Re-(int)(Re+0.5)) < eps && abs(Im) < eps;
            }
            if (ok) {
                cout << "Yes\n";
                break;
            }
        }
        if (!ok) {
            cout << "No\n";
        }
    }
    return 0;
}
回复
10175101159
6 年前

666

回复
10162100115
6 年前

求问怎么二分暴力测试样例数据？

回复
10175101159
6 年前

$emmmmmmm$
比如说，下午$E$题
你从$print(-1)$一直到$print(20)$
提交$22$次你就知道哪些测试点输出的是$-1$，哪些是$0$，$ect.$
然后你二分数据范围
很快就测出当$n$等于多少时输出这个值
（大雾

回复

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

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