首页 > 其他分享 >暑假集训7(建议等我改完再点开)

暑假集训7(建议等我改完再点开)

时间：2022-08-21 15:12:39浏览次数：51  
标签：ch const 改完 int 点开 ll pos 集训 getchar

A. One

用vector把out的及时删掉，然后就可以直接加位置了，STL真好用，不过它T了……

#include <bits/stdc++.h>
  
using namespace std;

int T, n;
vector<int> a;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    T = read(); 
    while(T--)
    {
        a.clear();
        n = read();
        for(int i=1; i<=n; i++)
        {
            a.push_back(i);
        }
        int sz = a.size(), p = 1, pos = 0;
        while(sz > 1)
        {
            pos += p-1;
            pos %= sz;
            //printf("pos = %d\n", pos);
            a.erase(a.begin()+pos);
            pos; p++;
            sz--;
        }
        printf("%d\n", a[0]);
    }
  
    return 0;
}
TLE 60

 

B. 砖块

看起来很麻烦的样子不想做怎么办……那就来一个k=1的特判吧……考完才发现是大水题……后悔了。

记录左下脚的位置和当前的状态，过程挺暴力的。

#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
const int maxn = 107;
const int N = 505;
const ll mod = 1e9 + 7;
const int inf = (1<<29);

int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

int T, k, b[104], a[2006][2006], n, ans, st;
char s[104];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()//k = 1
{
    T = read();
    while(T--)
    {
        k = read();
        scanf("%s", s+1);
        n = strlen(s+1);
        for(int i=1; i<=n; i++)
        {
            if(s[i] == 'E') b[i] = 1;
            else if(s[i] == 'W') b[i] = 2;
            else if(s[i] == 'N') b[i] = 3;
            else b[i] = 4;
        }
        memset(a, 0, sizeof(a));
        int x = 1000, y = 1000;
        a[x][y] = 1; ans = 1; st = 1;
        for(int i=1; i<=n; i++)
        {
            if(b[i] == 3)
            {
                if(st == 1)
                {
                    st = 2; x++;
                    for(int j=x; j<x+k; j++)
                    {
                        a[j][y]++;
                        //printf("a[%d][%d]++\n", j-100, y-100);
                        ans = max(ans, a[j][y]);
                    }
                    //printf("st = %d  %d  %d\n", st, y-100, x-100);
                }
                else if(st == 2)
                {
                    st = 1; x += k;
                    a[x][y]++;
                    //printf("a[%d][%d]++\n", x-100, y-100);
                    ans = max(ans, a[x][y]);
                }
                else 
                {
                    x++;
                    for(int j=y; j<y+k; j++)
                    {
                        a[x][j]++;
                        //printf("a[%d][%d]++\n", x-100, j-100);
                        ans = max(ans, a[x][j]);
                    }
                }
            }
            else if(b[i] == 1)
            {
                if(st == 1)
                {
                    st = 3; y++;
                    for(int j=y; j<y+k; j++)
                    {
                        a[x][j]++;
                        //printf("a[%d][%d]++\n", x-100, j-100);
                        ans = max(ans, a[x][j]);
                    }
                }
                else if(st == 2)
                {
                    y++;
                    for(int j=x; j<x+k; j++)
                    {
                        a[j][y]++;
                        //printf("a[%d][%d]++\n", j-100, y-100);
                        ans = max(ans, a[j][y]);
                    }
                }
                else 
                {
                    st = 1;
                    y += k;
                    a[x][y]++;
                    //printf("a[%d][%d]++\n", x-100, y-100);
                    ans = max(ans, a[x][y]);
                }
            }
            else if(b[i] == 2)
            {
                if(st == 1)
                {
                    st = 3; y -= k;
                    for(int j=y; j<y+k; j++)
                    {
                        a[x][j]++;
                        //printf("a[%d][%d]++\n", x-100, j-100);
                        ans = max(ans, a[x][j]);
                    }
                }
                else if(st == 2)
                {
                    y--;
                    for(int j=x; j<x+k; j++)
                    {
                        a[j][y]++;
                        //printf("a[%d][%d]++\n", j-100, y-100);
                        ans = max(ans, a[j][y]);
                    }
                }
                else 
                {
                    st = 1; y--;
                    a[x][y]++;
                    //printf("a[%d][%d]++\n", x-100, y-100);
                    ans = max(ans, a[x][y]);
                }
            }
            else 
            {
                if(st == 1)
                {
                    st = 2; x -= k;
                    for(int j=x; j<x+k; j++)
                    {
                        a[j][y]++;
                        //printf("a[%d][%d]++\n", j-100, y-100);
                        ans = max(ans, a[j][y]);
                    }
                }
                else if(st == 2)
                {
                    x--; st = 1;
                    a[x][y]++;
                    //printf("a[%d][%d]++\n", x-100, y-100);
                    ans = max(ans, a[x][y]);
                }
                else 
                {
                    x--;
                    for(int j=y; j<y+k; j++)
                    {
                        a[x][j]++;
                        //printf("a[%d][%d]++\n", x-100, j-100);
                        ans = max(ans, a[x][j]);
                    }
                }
            }
        }
        if(st == 1)
        {
            printf("%d\n", y-1000);
            printf("%d\n", x-1000);
        }
        else if(st == 2)
        {
            //printf("%d\n", y-1000);
            for(int i=x; i<x+k; i++)
            {
                printf("%d ", y-1000);
            }
            printf("\n");
            for(int i=x; i<x+k; i++)
            {
                printf("%d ", i-1000);
            }
            printf("\n");
        }
        else 
        {
            for(int i=y; i<y+k; i++)
            {
                printf("%d ", i-1000);
            }
            printf("\n");
            //printf("%d\n", x-1000);
            for(int i=y; i<y+k; i++)
            {
                printf("%d ", x-1000);
            }
            printf("\n");
        }
        printf("%d\n", ans);
    }
  
    return 0;
}
View Code

 

C. 数字

我只会把0去掉挨个乘*本来取模都是取的正好的，结果提交之前发现同一个数输出不同位不对应！？于是把它改大了一点……

#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
const int maxn = 24;
const int N = 505;

int k, T;
ll ans, n;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    T = read();
    while(T--)
    {
        scanf("%lld", &n);
        k = read();
        if(k == 1)
        {
            ll mod = 10000; ans = 1;
            for(int i=1; i<=n; i++)
            {
                ans *= i;
                //printf("pre : %lld   ", ans);
                while(ans % 10 == 0 && ans) ans /= 10;
                //printf("ans = %lld\n", ans);
                ans %= mod;
                //printf("%lld\n", ans);
            }
            ans %= 10;
            printf("%lld\n", ans);
        }
        if(k == 2)
        {
            ll mod = 10000; ans = 1;
            for(int i=1; i<=n; i++)
            {
                ans *= i;
                while(ans % 10 == 0 && ans) ans /= 10;
                ans %= mod;
            }
            ans %= 100;
            if(ans / 10 == 0) printf("0");
            printf("%lld\n", ans); 
        }
        if(k == 3)
        {
            ll mod = 10000; ans = 1;
            for(int i=1; i<=n; i++)
            {
                ans *= i;
                while(ans % 10 == 0 && ans) ans /= 10;
                ans %= mod;
            }
            ans %= 1000;
            if(ans / 100 == 0) printf("0");
            if(ans / 10 == 0) printf("0");
            printf("%lld\n", ans);
        }
    }
  
    return 0;
}
TLE 20

 

D. 甜圈

我用线段树标记了一下区间合法的数目，区间进行到的步骤，区间进度是否一致，还有一个lazy，结果它T了……当我听说比较高级的暴力都拿到了70 eps的时候……啊不过我不后悔搞了棵树，因为我不知道怎么暴力。

#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
const int maxn = 2e5 + 4;
const int N = 505;
const ll mod = 1e9 + 7;
const int inf = (1<<29);

int n, k, m, ans;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    int sum, col, lazy, only;
}t[maxn<<2];

void pushup(int x)
{
    t[x].sum = t[x<<1].sum + t[x<<1|1].sum;
    //printf("pushup: t[%d].sum = %d\n", x, t[x].sum);
    if(t[x<<1].col == t[x<<1|1].col && t[x<<1].only && t[x<<1|1].only)
    {
        t[x].only = 1; t[x].col = t[x<<1].col;
    }
    else 
    {
        t[x].col = -1; t[x].only = 0;
        //printf("t[%d].only = 0\n", x);
    }
}

void build(int x, int l, int r)
{
    if(l == r)
    {
        t[x].sum = 1; t[x].only = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    pushup(x);
}

void pushdown(int x, int l, int r)
{
    int ls = x<<1, rs = x<<1|1;
    if(t[x].lazy == 1)
    {
        t[ls].col = t[rs].col = t[x].col;
        //printf("t[%d].col = t[%d].col = %d\n", ls, rs, t[ls].col);
        t[ls].lazy = t[rs].lazy = 1;
    }
    else if(t[x].lazy == -1)
    {
        t[ls].col = t[rs].col = -1;
        t[ls].lazy = t[rs].lazy = -1;
        t[ls].sum = t[rs].sum = 0;
        //printf("t[%d] and t[%d] is cleaned\n", ls, rs);
    }
    t[x].lazy = 0;
}

void update(int x, int l, int r, int L, int R, int col)
{
    //printf("update(%d, %d, %d, %d, %d, %d)\n", x, l, r, L, R, col);
    if(L <= l && r <= R)
    {
        if(t[x].only)
        {
            if(t[x].col == col-1)
            {
                t[x].col = col; t[x].lazy = 1;
                //printf("t[%d].col = %d\n", x, t[x].col);
                return;
            }
            else 
            {
                t[x].col = -1; t[x].sum = 0;
                //printf("t[%d] is cleaned\n", x);
                t[x].lazy = -1;
                return;
            }
        }
    }
    if(t[x].lazy) pushdown(x, l, r);
    int mid = (l + r) >> 1;
    if(L <= mid) update(x<<1, l, mid, L, R, col);
    if(R > mid) update(x<<1|1, mid+1, r, L, R, col);
    pushup(x);
}

int main()
{
    n = read(); k = read();
    build(1, 1, n);
    m = read();
    while(m--)
    {
        int l = read(), r = read(), col = read();
        update(1, 1, n, l, r, col);
    }
    update(1, 1, n, 1, n, k+1);
    /*for(int i=1; i<=9; i++)
    {
        printf("t[%d].sum = %d\n", i, t[i].sum);
    }*/
    ans = t[1].sum;
    printf("%d\n", ans);
  
    return 0;
}
TLE 70

 

标签：ch,const,改完,int,点开,ll,pos,集训,getchar
From： https://www.cnblogs.com/Catherine2006/p/16610033.html

相关文章

  • 集训3/4总结
    这几次考试题难度和在家集训五天的难度差不多，但是考试状态好了很多，故成绩还看得过去。感觉基本集训几天第一次学的算法都没太学懂，还需要自己去复习。上新课的速度没我想的......
  • 集训总结
    集训总结收获学习了一些从未接触的数据结构：线段树，树状数组，单调栈，单调队列可以实现一些基本操作，但与灵活运用还有一定距离，也无法与其他算法相结合使用提升了图......
  • A层邀请赛6 && 暑假集训加试1
    A.菜暴力做法：2^n枚举哪些人是正向上菜的，然后记录答案。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=20;constin......
  • 2022暑假集训总结
    经过简介7月20日到达内江天立学校，在小学部的机房上课。这里没什么人，比较安静，也没有那么热，学习环境挺好的。开始是老姚给我们上的课，主要讲了tarjan，然后由几位学长讲课。期......
  • 2022暑假集训总结
    2022暑假集训总结收获做了██道题跟着多校联训学的时候，主要收获是学会了一些基本的暴力算法和一些以前不知道的算法概念后来高烧休息了几天回来以后主要的收获是考试......
  • 暑假集训6
    前两题只会打暴力，本来以为又要垫底了，结果还可以？A.接力比赛确实是背包，排序后每次跑上界为\(\sumw_i\),然后刚刚好卡过？？随机数据跑的还是挺快的code#include<cstring>......
  • 暑假集训六[接力比赛,树上竞技,虚构推理,记忆碎片]
    暑假集训六接力比赛我是真没想到这玩意还能跟背包扯上关系，学到了但这里写的不是题解的做法，这里写的是类似的一种解法考虑\(dp\)的定义\(dp[1/0][j]\)表示\(0\)......
  • 暑假集训六 [接力比赛，树上竞技，虚构推理，记忆碎片]
    暑假集训六别问为什么从六开始。题面A.接力比赛两个01背包跑一遍。别问代码为啥写的这么阴间。Code#include<cstdio>#include<algorithm>usingnamespacestd;......
  • 暑期集训6
    rank19mark70题纲：T1：接力比赛（DP优化（随机化+上界递增优化））；T2：树上竞技：计数类DP；T3：思维（暴力找max距离的优化：从最大距离的一遍反着找最近的距离点对）；T4：神仙图DP....由于进度......
  • [游记]暑假集训6-2022
    久违的Rank1A. 接力比赛比较显然的$\operatorname{DP}$，两个$01$背包解决问题  #include<cstdio>#include<cstring>#include<string>#defineWRWinterRa......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99