UOJ Logo cyx的博客

博客

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

总结

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

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。