2019 3 18 杭师大ACM游记

杭师大ACM总结

只有两个人打个球球啊

因为只有两个人所以题都没开完，题目翻译比别的组慢了不知道多少，讨论聪明题的时候也少一张口胡爷的嘴巴

T1

水题，字符串输入
然而我getchar搞了半小时也没对，然后gets（）一发过了

T2

最喜欢的一题 问在一个区间里能不能找到三个数满足a+b>c
也就是说如果要一直不满足就要使序列满足a+b<=c
也就是极端情况就是一个从1 1开始的斐波那契数列
但斐波那契到了60多项就是非常大了，所以区间在60以内暴力判
60以上直接”YES”

#include<iostream>
using namespace std;
long long read()
{
    long long tot=0,fs=1;
    char ch;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') ch=getchar(),fs=-1;
    while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
    return tot*fs;
}
long long a[500009];
long long n,q; 
int main()
{
    n=read(),q=read();
    for(long long i=1;i<=n;i++) a[i]=read();
    for(long long iii=1,l,r;iii<=q;iii++)
    {
        l=read(),r=read();
        if(l>r||l<0||r<0)
        {
            printf("NO\n");
            continue;    
        }
        if(r-l<=60)
        {
            bool kx=0;
            for(long long i=l;i<=r;i++)
            {
                for(long long j=i+1;j<=r;j++)
                { 
                    for(long long k=j+1;k<=r;k++)
                    {
                        long long ls1=a[i],ls2=a[j],ls3=a[k];
                        if(ls1>ls2) swap(ls1,ls2);
                        if(ls1>ls3) swap(ls1,ls3);
                        if(ls2>ls3) swap(ls2,ls3);
                        if(ls1+ls2>ls3) kx=1;    
                    }
                }
            }
            if(kx) printf("YES\n");
            else printf("NO\n");
        }
        else
        {
            printf("YES\n");    
        }
    }
    return 0;
}

T3

题意:对所有数异或 与 或 一些数
然后求区间第k大
一看就知道是可持久化数据结构（然而我只会主席树）
正解是可持久化01树异或直接暴力重构
我也不知道怎么写 过

T4

问数列里有几个不同的数字
水题，过

T5

从0出发，每次只能跳到(i2)%n或者(i2+1)%n，求字典序最大的汉密尔顿回路。
显然汉密尔顿回路需要状压 这里n太大不合适
首先n为奇数时绝对无解（为什么）
因为在奇数的情况下，只有(n-1)/2能与n-1和0连边也就是说(n-1)/2这个点要经过两次，不成立
当n是偶数，可以发现i和i+n/2的出边完全相同。
我们把i和i+n/2合并，得到一张n/2个点的图，所有点都需要两条入边和两条出边——欧拉回路！
于是只需要跑出欧拉回路就能对应到原问题了，介于欧拉回路算法的性质，贪心走较大的边即可保证字典序最大。

T6

搞不懂 告辞

T7

你有一个钱罐子，每天放进去的钱是不降的，如果在第k天时，你恰好有a[k]元，则可以选择将钱罐子清空然后获得v[k]的贡献值
显然选择一个罐子时你放入的钱要尽可能少，则将钱分平均（上取整）
然后当你选择的商品为k1,k2,k3……kn时
必然满足a[ki]/(ki-ki-1)<=a[ki-1]/(ki-1-ki-2) （上去整）
令f[i][j]表示最后购买的两个物品为i和j，则f[i][j]=max(f[j][k]+v[i]) (j->k->i合法)
这样枚举需要多一个k
已知两个不等式三个未知数，显然可以表示1个
于是我们得到k>=j-(i-j)*a[j]/a[i]
也就是可选取的k在一个区间内，而且是一直到结尾的，所以直接把v[i]扔出去
设s[j][k]为f[j][k..j]的最大值（因为满足决策单调性）
那么max就被去掉了

//不知道为什么错了。。。
#include<iostream>
using namespace std;
long long read()
{
    long long tot=0,fs=1;
    char ch;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') ch=getchar(),fs=-1;
    while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
    return tot*fs;
}
int n;
int w[2009],v[2009];
int f[2009][2009],s[2009][2009];
int ans;
int main()
{
    n=read();
    for(int i=1;i<=n;i++) w[i]=read();
    for(int i=1;i<=n;i++) v[i]=read();
    for(int i=1;i<=n;i++)
    {
        f[i][0]=v[i];
        ans=max(ans,v[i]);    
    }
    for(int i=2,k;i<=n;i++)
    {
        if(w[i]==0) continue;
        for(int j=1;j<i;j++)
        {
            k=max(0,j-(i-j)*w[j]/w[i]);
            if(k<j) f[i][j]=s[j][k]+v[i],ans=max(ans,f[i][j]);
        }
        for(int j=i-1;j>=0;j--)
        {
            s[i][j]=max(s[i][j+1],f[i][j]);    
        }
    }
    cout<<ans;
    return 0;
}

T8

问对于每个i
ai^aj>aj^ai的组数有多少
我在考场愉快的得到一个式子
ylnx > xlny
然后我竟然傻了去找规律！
论三个人的好处都有啥？
移一下项就可以得到y/lny > x/lnx
哇，那排序不就好了嘛
今天的wenjing233死于精度误差
我们考虑y=x/lnx的单调性
对其求导（我不会，实际上我打表找到的规律似乎与这个差不多，但似乎我不小心把4给特判错了，实际上4是普遍性的）(无端迫害米4达，自裁，请）
补个图
也就是2等价于4
2^4=4^2
以及1视为无限小
也就是说把2变成4然后排序，去重并记录个数就好了

T9

感谢xyc大佬对本题的贡献
题意是给定明文和秘文，明文字母表与秘文字母表一一对应
问有哪些明文字母与密文字母对应关系已知或输出不可能
坑点在于，已知25组关系下，第26组是知道的！！！

T10

傻逼题，题意都不想说

T11

水题干他妈的徐元程
给出一些点问面积在l——r之间的三角形有多少
本来已经想出来就是把所有三角形算出来然后排序二分就完美了，结果xyc硬说1e7排序超时
然后我就从对n立方级别的排序拆成n个n方排序（也就是对于每个点进行储存）这样就省了一个log（n）,但是这样会多一个6因为三角形重复计数

T12

开都没开。。。
不想订正了。。。

T13

这个要挖坑，先把PPT的东西搬过来
SG函数还是要好好学学的

题意：石子游戏，要不取一堆，要不取x个且gcd(x,该堆石子个数)=1，问谁会赢。

题解：显然符合NIM游戏，只要能算出sg函数值即可判断。
    打表寻找规律，可以发现当x为质数时，sg[x]=x是第几个质数+1。
                当x不为质数时，sg[x]=sg[p]且p是x的最小质因子。

    写一个类似线性筛的循环即可，线性筛保证每个数字都是被最小质因子筛到。

让人自行思考的出题人是人间之屑（暴论）

完结扬出题人骨灰（大误）

也就是说要补的代码有T 2 5 7 8 11

不想补了。。。有缘再相见吧。。。