这是给大一acm训练出的考试题题解。
题目名字有“jwGG”的3道题,是我出的(jwGG的签到题jwGG与yzMM的字符串jwGG与bwMM的字符串),
其他的题是实验室各位大佬出的。
感谢所有出题人的付出。

@[TOC]

nefu 2133 jwMM的疯狂A-B

签到题。两个set,直接模拟。

#include <bits/stdc++.h>
using namespace std;
set<int>s1,s2;
int n,m,x,flag=0;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        s1.insert(x);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x;
        s2.insert(x);
    }
    for(auto it=s1.begin();it!=s1.end();it++)
        if(!s2.count(*it))flag=1,printf("%d\n",*it);
    if(!flag)printf("So crazy!!!\n");
    return 0;
}

nefu 2122 熊熊对对碰

注意特判x=0,y=0,只计算一次。二维数组可以用map套map,或者map套pair来写。
用auto可以自动推断变量类型。

方法1,map套pair。

#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>,int>vis;
int n,x,y,num,ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    while(n--)
    {
        cin>>x>>y;
        vis[{x,y}]++;
    }
    for(auto i=vis.begin();i!=vis.end();i++)
    {
        x=i->first.first;
        y=i->first.second;
        if(x==0&&y==0)num=vis[{x,y}];
        else num=vis[{x,y}]+vis[{-x,-y}];
        if(!(num&1))
        {
            ans+=num;
            vis[{x,y}]=0;
            vis[{-x,-y}]=0;
        }
    }
    printf("%d\n",ans);
    return 0;
}

方法2,map套map。

#include <bits/stdc++.h>
using namespace std;
map<int,map<int,int> >vis;
int n,x,y,num,ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    while(n--)
    {
        cin>>x>>y;
        vis[x][y]++;
    }
    for(auto i=vis.begin();i!=vis.end();i++)
        for(auto j=i->second.begin();j!=i->second.end();j++)
        {
            x=i->first;
            y=j->first;
            if(x==0&&y==0)num=vis[x][y];
            else num=vis[x][y]+vis[-x][-y];
            if(!(num&1))
            {
                ans+=num;
                vis[x][y]=0;
                vis[-x][-y]=0;
            }
        }
    printf("%d\n",ans);
    return 0;
}

nefu 2120 秘籍

这题可以前缀和,map标记某个区间内和是否等于k;或者也可以双指针尺取去做。

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,k,l,r,a[N];
bool judge()
{
    int tmps=0;
    for(l=1,r=1;r<=n;r++)//尺取
    {
        tmps+=a[r];
        while(tmps>k&&l<r)tmps-=a[l],l++;
        if(tmps==k)return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    if(judge())printf("%d %d\n",l,r);
    else printf("tiangeniupi\n");
    return 0;
}

nefu 2103 jwGG的签到题

化简公式可得 $10^{leny}=y+1$,leny表示y的长度,y=(int)log10(y)+1
同时取以10为底的对数得 $leny=log10(y+1)$,即:$log10(y)+1=log10(y+1)$

打表找规律即可,打表代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    for(int i=1;i<=1e5;i++)
    {
        int x=(int)log10(i+1);
        int y=(int)log10(i)+1;
        if(x==y)printf("%d\n",i);
    }
    return 0;
}

打表输出:

9
99
999
9999
99999

x可以取[1,a]内所有值,所以只需要找y能取多少种,y可取的种数就是看小于y的连续9组成的数有多少个,答案相乘即可。
答案最大是18*1e18,会爆long long,应该开unsigned long long。

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll T,a,b,s[20];
int main()
{
    ios::sync_with_stdio(false);
    for(int i=1;i<=18;i++)//打表9,99,999,9999...(一直到18个9)
        s[i]=s[i-1]*10+9;
    cin>>T;
    while(T--)
    {
        cin>>a>>b;
        ll k=upper_bound(s+1,s+18+1,b)-s-1;
        printf("%llu\n",a*k);
    }
    return 0;
}

nefu 2126 煊哥的难题

两条直线至少有一个交点,也就是重合或者相交。
i 从 1 到 n 遍历一遍所有直线,每次 ans += i - 1 - 平行Li的个数。
平行的个数可以用map标记,斜率k相等并且截距b不等的两直线满足平行关系。

方法1,标记斜率k和截距b。注意特判斜率不存在的情况。
double类型当map的键,如果只进行了一次除法运算得到k,在1e9范围内精度是可行的。
(当然,为了保险,建议还是用把斜率化成最简分数a/b保存起来。)

double存斜率做法:

#include <bits/stdc++.h>//368ms
using namespace std;
typedef long long ll;
map<double,int>vis1;//记录k值相等的直线,平行或者重合
map<double,map<double,int> >vis2;//记录k和b都相等的直线,重合
map<double,int>chuizhi;//记录垂直x轴的直线的横坐标
int n,num0;
double X1,X2,Y1,Y2,dx,dy;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>X1>>Y1>>X2>>Y2;
        dx=X2-X1;
        dy=Y2-Y1;
        if(dx==0)//斜率无穷大,直线垂直于x轴,这些直线一定都平行
        {
            int dnum=num0-chuizhi[X1];//平行
            ans+=i-1-dnum;
            num0++;//平行或重合
            chuizhi[X1]++;//重合
        }
        else
        {
            double k=dy/dx;//斜率
            double b=Y1-k*X1;//截距
            int num1=vis1[k];//平行或重合
            int num2=vis2[k][b];//重合
            int dnum=num1-num2;//平行
            ans+=i-1-dnum;
            vis1[k]++;
            vis2[k][b]++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

方法2,标记直线的一般式ax+by+c=0中的系数a,b,c,注意先对a,b进行化简,都除以gcd(a,b)化成最简分数。
map标记三个系数,相当于三维数组标记,映射过程多,导致时间长一些。

#include <bits/stdc++.h>//407ms
using namespace std;
typedef long long ll;
map<ll,map<ll,map<ll,ll>> >vis1;
map<ll,map<ll,ll> >vis2;
ll n,ans,X1,Y1,X2,Y2,dx,dy;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>X1>>Y1>>X2>>Y2;
        dx=X2-X1;
        dy=Y2-Y1;
        ll k=__gcd(dx,dy);
        dx/=k;
        dy/=k;
        ll num1=vis1[dy][dx][Y1*dx-X1*dy];//重合
        ll num2=vis2[dy][dx];//平行或重合
        ll dnum=num2-num1;//平行
        ans+=i-1-dnum;
        vis1[dy][dx][Y1*dx-X1*dy]++;
        vis2[dy][dx]++;
    }
    printf("%lld\n",ans);
    return 0;
}

nefu 2106 jwGG与yzMM的字符串

直接模拟。预先打表,得到解码表。

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e5+10;
int n,m;
char s[N][N],a[60],ans[130][130];
struct node
{
    int x,y;
}p[M];
void init()//打表,预处理
{
    for(int i=0;i<=51;i++)
    {
        if(i<=25)a[i]=i+'A';
        else a[i]=i+'a'-26;
    }
    for(int i=0;i<=51;i++)//打表解码表
        for(int j=0;j<=51;j++)
        {
            int z=(i+j)%52;
            ans[a[j]][a[z]]=a[i];
        }
}
int main()
{
    ios::sync_with_stdio(false);
    init();
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>p[i].x>>p[i].y;
    for(int i=1;i<=n;i++)
        cin>>s[i];
    for(int i=m;i>=1;i--)//倒序解密
    {
        int x=p[i].x;
        int y=p[i].y;
        int len1=strlen(s[x]);
        int len2=strlen(s[y]);
        for(int j=0;j<len2;j++)
            s[y][j]=ans[s[x][j%len1]][s[y][j]];
    }
    for(int i=1;i<=n;i++)
        printf("%s\n",s[i]);
    return 0;
}

nefu 2107 jwGG与bwMM的字符串

推导公式,遍历一下字符串得到满足条件的个数。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s[N];
int n,t,x,num0,num1,flag,p[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n>>x>>s;
        num0=0,num1=0,flag=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='0')num0++;
            else num1++;
            p[i]=x+num1-num0;
        }
        int ans=0;
        if(x==0)ans++;//注意特判空串
        for(int i=0;i<n;i++)
        {
            if(num0==num1)
            {
                if(p[i]==0){flag=1;break;}
                else continue;//p[i]!=0
            }
            if(p[i]%(num0-num1)==0&&p[i]/(num0-num1)>=0)ans++;
        }
        if(flag)printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}

nefu 2133 库特放书

这题不能二分,因为不具备单调性(可以自己打表试试)。

出题人gls 解释为什么可以直接暴力模拟,并且不会超时:

H题再解释一下为什么直接暴力不用二分在时间上是可行的吧,因为我看所有通过代码都写的枚举容量的上界是sum,但是如果上界真的是sum的话在时间上理论上是不可行的,这一点上并不是我数据出水了,是它的下界可以视为max(ceil(sum/ k),maxV),上界为ceil(sum / k)+MAXV
所以枚举次数为二者之差远达不到sum次,最多也不会超过1000次所以从下界while(1)向上寻找在时间上是可行的

用vector模拟的代码(数组模拟/multiset模拟均可)

#include <bits/stdc++.h>//656ms
using namespace std;
vector<int>s;
int T,n,m,x,ans,cas;
bool judge(int mid)//体积为mid时
{
    vector<int>tmp=s;//tmp为书的集合(已排序)
    int cnt=1,rest=mid;//cnt记录当前体积需要多少箱子才能放下所有书,rest记录每个箱子还剩多少体积
    while(tmp.size())
    {
        if(cnt>m)return 0;
        int k=upper_bound(tmp.begin(),tmp.end(),rest)-tmp.begin()-1;//找小于等于rest的第一个元素下标
        if(k==-1)cnt++,rest=mid;//没有小于等于rest的,这个箱子已经放不下了,另外放一个箱子
        else//能放下,放进箱子,并删除这本书
        {
            rest-=tmp[k];
            tmp.erase(tmp.begin()+k);
        }
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        s.clear();
        int mx=0,sum=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            mx=max(mx,x);
            sum+=x;
            s.push_back(x);
        }
        if(m>=n)printf("Case #%d: %d\n",++cas,mx);//特判m>=n
        else
        {
            sort(s.begin(),s.end());
            int l=(int)ceil(1.0*sum/m);//下界
            for(int i=l;;i++)
                if(judge(i)){ans=i;break;}
            printf("Case #%d: %d\n",++cas,ans);
        }
    }
    return 0;
}