UOJ Logo cyx的博客

博客

游记

2020-06-20 19:42:50 By cyx

day1

凉凉

Q·H·C 模拟赛总结及题解

2019-08-25 18:17:04 By cyx

比赛问题

题面出锅, 签到题题面打错了

题目总结

A. 数字问题

此题为签到题。

只包含简单数学内容(模运算)

题解:
题目重点是对9取模。
我们知道 pow(10, x) mod 9 = 1
因此我们只需要考虑每一位上的数字即可
例如 91011
对位数分解得 9 * 10^4 + 1 * 10^3 + 0 * 10^2 + 1 * 10 + 1
该数对9取模与(9 + 1 + 0 + 1 + 1)->( 3 )同余
运用上述原理可省略计算每一位上的数字,直接计算Ans,时间复杂度O(1)
简化-> [L,R] -> Ans = ( (L + R) * (R - L + 1) / 2 ) % 9;
需要求解乘法逆元保证无误差。

B. 数字对

此题主要为整除性质提供的贪心题。

题解:
x|y , y|z -> x|z
因此我们可以对序列数字排序,由小至大进行求解。
对每一个数进行向左和向右的扫描,若为倍数进行区间的扩展并标记区间内的数字,Ans 取最大区间长度
可以证明:
    若数x已被标记,则以数x扩展的区间不可能比先前扩展的区间长,因此可直接跳过该数
时间复杂度O(n)

部分写法存在重复计数的问题,上述方法只记录一次,保证不重不漏。

C. 序列

此题对对称性进行了简单的考察。

提供30pts+的暴力分。

题解:
对于一个二进制数,对其翻转(异或)偶数次与原数相同
因此,可以建立一个可以区间修改单点查询的数据结构(树状数组或线段树,etc)
每次操作记录每个点的操作次数,在查询时判断奇偶对数字进行操作
每组操作结束后再对所有数字进行更新(我没想到更快的办法)


-------------------
对于按位取反我们有如下方法:

1·预处理数组f[i] = 1 << i - 1;
2·运用补码反码
    对数x
    取tmp = -x - 1
    此时tmp 的2进制已经是 x的取反;
    为了保证我们取到后n位
    我们定义一个无符号变量存储这串数字并取余即可
    x   -> 00101011
    -x  -> 11010101
    tmp -> 11010100
    首位为符号位

D. 数字操作

简单送分题

两种写法:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int a[30005],ans[5000010],topa,topans,next[5000010];
int main()
{
    int l,m;
    cin>>l>>m;
    memset(ans,0x3f,sizeof(ans));
//先将ans设置最大,删除时如果是递减序列方便特判。
    q.push(1);
    while(1)
    {
        int x=q.top(),d=0;q.pop();
        q.push(2*x+1);q.push(4*x+5);  
        a[++topa]=x;//记录输入的数
        while(x)
        {
            d=d*10+x%10;
            x/=10;
        }//反向拆解
        while(d)
        {
            ans[++topans]=d%10;
            d/=10;
        }//将数字一位位加入ans
        if(topa>=l) break;//到限度停止加入
    }
    for(int i=1;i<=topa;i++) cout<<a[i];
    cout<<endl;
    for(int i=0;i<topans;i++) next[i]=i+1;
//模拟链表,记录当前位的下一位的位置,方便比较,就不用删数了
    while(m)
    {
        int l=0;
        while(ans[next[l]]>=ans[next[next[l]]])
//末尾不用特判,因为一定不会比0x3f大
            l=next[l];//直到出现前比后小
        next[l]=next[next[l]];
        m--;
    }
    for(int i=0;next[i];i=next[i]) cout<<ans[next[i]];
    return 0;
}
#include<iostream>
#include<cstdio>
using namespace std;
bool a[4232449];
int num[30010], cnt;
int k, m;
int main(){
    a[1] = 1;
    num[1] = 1;
    int cnt = 1;
    for(int i = 2; i <= 4232447; i++){//该上限可预处理计算
        if((i - 1 >= 2) && ((i - 1) % 2) == 0)
            if(a[(i - 1) / 2])    a[i] = 1;
        if((i - 5 >= 4) && ((i - 5) % 4) == 0)
            if(a[(i - 5) / 4])    a[i] = 1;
        if(a[i])    {
            cnt++;
            num[cnt] = i;
        }
    }
    cin >> k >> m;
    for(int i = 1; i <= k; i++)
        printf("%d",num[i]);
    printf("\n");
    int isdown = 0;
    int que[30010], l = 0, r = 0;
    for(int i = 1; i <= k; i++){
        int w = 0;
        int val[10];
        if(isdown == m){
            printf("%d",num[i]);
            continue;
        }
        while(num[i]){
            val[++w] = num[i]%10;
            num[i] /= 10;
        }
        for(int j = w; j >= 1; j--){
            if(isdown < m){
                while(l < r && que[r] < val[j] && isdown < m){
                    r--;isdown++;
                }
                que[++r] = val[j];
                if(isdown == m)    {
                    for(int ls = l + 1; ls <= r; ls++)
                        printf("%d",que[ls]);
                }
            }
            else{
                printf("%d",val[j]);
            }
        }
    }
    return 0;
}

关于DYA2

比day1还简单,不用题解了
T3 -> 洛谷P3365

总结

基本上都是只用到基本数学原理的题,比较简单

KFC

2019-08-24 08:49:38 By cyx
既然NOIp没了,变成了CSP,那么以后AFO(Away From OI)就应该说成AFC(Away From CSP)

也可以表达为KFC(Kicked From CSP),而KFC同样指肯德基…

所以OI的本质依然是肯德基三人篮球赛

DP-Problems

2019-05-25 18:36:53 By cyx

[一]树形DP

1.bzoj2286消耗战

2.bzoj1827奶牛大集会

3.bzoj1596电话网络

4.bzoj1864三色二叉树

5.bzoj1060时态同步

6.bzoj2435道路修建

7.bzoj2427软件安装

8.bzoj1369GEM

9.bzoj3573米特运输

10.bzoj3522Hotel

[二]区间DP

1.bzoj1260涂色

2.bzoj1090字符串压缩

3.bzoj1068压缩

[三]状压DP

1.bzoj1725牧场的安排

2.bzoj1087互不侵犯king

3.bzoj1688疾病管理

4.bzoj2073PRZ

5.bzoj1231混乱的奶牛

6.bzoj1072排列

WEEK2--T3

2019-03-23 08:32:05 By cyx

本题正解采用'树上DP'的做法。

如果按照最短路算法,那么时间复杂度将会达到$N^2logN$。

这样显然是会TLE。

那么我们需要更改我们的算法。

我们先从简单入手

对于 $m=0$ 的情况。

我们令

        Ans[i]:第i点到各点的距离和。
        F[i]:第i点的父亲结点

那么对于Ans[i],我们可以通过$Ans[F[i]]-dis*size[i]+dis*(size[f[i]]-size[i])$求得(原理为将父节点先转化为子节点,再累加)dis:点i与其父亲结点的距离,size[i]:点i子树结点数。

通过画图很容易理解,也很容易看出其无后效性的特点。

那么现在我们其实只需要两遍DFS即可解题。

第一遍我们以 1 为根进行遍历,求得Ans[1];

第二遍DFS我们可通过上述状态转移方程进行求解每一个点

时间复杂度O(N)

异或问题

上述方法虽然压缩了时间复杂度,但却只能解决 $m=0$ 即不异或的问题。

对于需要进行异或的我们仍无法解决。

现在,我们对异或特点进行分析:

    如果数x与15进行异或
    (15) = (00001111)
    能够发现 ^ 运算只会对二进制后四位产生影响

那么我们依旧可以使用上述转移方程进行求解,但需要将后四位单独运算。

我们令:

    g[i]:第i点Ans 5位之后的大小
    f[i][k]:第i点 Ans 后4位大小为k的个数(边数)(代替上述size)

可得到:$Ans[i]=g[i]+\Sigma( k\ xor\ m )*f[i][k]$

我们首先进行预处理:

    dfs1(int x,int fa)
{
    for(int i=last[x];i;i=e[i].next)
        if(e[i].to!=fa)
        {
            dfs1(e[i].to,x);
            //加入该点与其儿子的连接
            g[x]+=g[e[i].to]+e[i].v/16;
            f[x][e[i].v%16]++;
            //加入其儿子的子叶与其的连接
            //遍历后四位数字:0~15
            for(int j=0;j<16;j++)
            {
                int k=j+e[i].v;
                g[x]+=k/16*f[e[i].to][j];
                f[x][k%16]+=f[e[i].to][j];
            }
            //计数原理:(a+b)%k=(a%k+b)k
        }
}

预处理需要将每个点与其子叶间的关系求得。

即此时g[i] f[i][k]只加入了第i点的子叶。

第二边DFS遍历,即可对每一个值进行更新

我们依旧采用最初的状态转移方程。

            int tmp=g[x]-g[e[i].to];
            for(int j=0;j<16;j++)
            {
                int k=j+e[i].v;
                tmp-=k/16*f[e[i].to][j];
                t[k%16]=f[x][k%16]-f[e[i].to][j];
            }
            t[e[i].v%16]--;
            g[e[i].to]+=tmp;
            f[e[i].to][e[i].v%16]++;

我们将该点(e[i].to)的父节点,转化为其字节点存入tmp,t[k]中。

转换方式与原来相同,减去父节点与其子叶间多余的dis。

第二遍DFS:

void dfs2(int x,int fa)
{
    for(int i=last[x];i;i=e[i].next)
        if(e[i].to!=fa)
        {
            int tmp=g[x]-g[e[i].to];
            for(int j=0;j<16;j++)
            {
                int k=j+e[i].v;
                tmp-=k/16*f[e[i].to][j];
                t[k%16]=f[x][k%16]-f[e[i].to][j];
            }
            t[e[i].v%16]--;
            g[e[i].to]+=tmp;
            f[e[i].to][e[i].v%16]++;
            for(int j=0;j<16;j++)
            {
                int k=j+e[i].v;
                g[e[i].to]+=k/16*t[j];
                f[e[i].to][k%16]+=t[j];
            }
            dfs2(e[i].to,x);
        }
}
cyx Avatar