四月做题

做题记录

二二年4.2

NOIP2011 提高组 铺地毯

题目

  • 标签 ：模拟，暴力枚举。

  • 题意 ：铺地毯， 求 \((x,y)\) 的地毯编号。

  • 数据范围 ：\(0?n?10^4,0?a,b,g,k?10^5\)。

  • 做法 ： 倒着枚举地毯，如果当前点在地毯中，输出答案即可。

分数 ： \(100\)。

code 
/**********
2022.4.2
kroyosh
luogu
P1003 [NOIP2011 提高组] 铺地毯
模拟，暴力枚举
**********/
#include 
#include 
#include 
#include 
#include 

using namespace std;

inline void rd(int &a)
{
    int r = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9')
    {
        r = r * 10 + (c - '0');
        c = getchar();
    }
    a = r * f;
}

const int N = 1e4 + 10;

int n, x[N], y[N], h[N], s[N], qx, qy;

int main()
{
    rd(n);
    for (int i = 1; i <= n; i ++ )
        rd(x[i]), rd(y[i]), rd(h[i]), rd(s[i]);
    rd(qx), rd(qy);
    for (int i = n; i; i -- )
    {
        if (x[i] <= qx && qx <= x[i] + h[i] && y[i] <= qy && qy <= y[i] + s[i])
        {
            printf("%d\n", i);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

二二年4.4

luogu P1989 无向图三元环计数

题目

  • 标签 ：图论， 三元环。

  • 题意 ：求无向图的三元环个数。

  • 数据范围 ：\(1?n?10^5,1?m?2×10^5,1?u, v?n\)。

  • 做法 ： 对无向图定向，设 \(deg[i]\) 为 \(i\) 点的度数，若 \(deg[a] < deg[b]\) 或者 \(deg[a] == deg[b]\) 并且 \(a < b\) ，则连一条从 \(a\) 到 \(b\) 的边， 否则连一条从 \(b\) 到 \(a\) 的边。枚举点 \(i\) ，将点 \(i\) 的所有出边打上标记，然后枚举 \(i\) 的出边 \((i,j)\) ，再枚举 \(j\) 的出边 \((j,k)\) ，如果 \(k\) 的标记是 \(i\) ，答案加 \(1\)。

分数 ： \(100\)。

code 
/**********
2022.4.4
kroyosh
luogu P1989 无向图三元环计数
三元环
**********/

#include 
#include 
#include 
#include 

#define gc getchar

using namespace std;

inline void rd(int &a)
{
    int r = 0, f = 1;
    char c = gc();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = gc();
    }
    while ('0' <= c && c <= '9')
    {
        r = (r << 3) + (r << 1) + (c - '0');
        c = gc();
    }
    a = r * f;
}

const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int h[N], e[M], ne[M], idx;
int a[M], b[M];
int dfn[N], deg[N];
int ans;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{
    memset(h, -1, sizeof h);
    rd(n), rd(m);
    for (int i = 1; i <= m; i ++ )
    {
        rd(a[i]), rd(b[i]);
        deg[a[i]] ++ ;
        deg[b[i]] ++ ;
    }
    for (int i = 1, x, y; i <= m; i ++ )
    {
        x = a[i], y = b[i];
        if (deg[x] > deg[y] || (deg[x] == deg[y] && x < y))
            add(x, y);
        else add(y, x);
    }
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
            dfn[e[j]] = i;
        for (int j = h[i]; ~j; j = ne[j])
            for (int k = h[e[j]]; ~k; k = ne[k])
            if (dfn[e[k]] == i) ans ++ ;
    }
    printf("%d\n", ans);
    return 0;
}

二二年4.6

NOIP1998 提高组 车站

题目

  • 标签 ：数学， 斐波那契。

  • 题意 ：第 \(1\) 站上车 \(a\) 人，第 \(2\) 站上，下车人数相同， 第 \(3\) 站及以后上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数， 求第 \(x\) 站开出时车上的人数。

  • 数据范围 ：\(1?a?20,1?x?n?20,1?m?2×10^4\)。

  • 做法 ： 推式子，具体见代码。

分数 ： \(100\)。

code 
/**********
2022.4.6
kroyosh
luogu P1011 [NOIP1998 提高组] 车站
数学， 斐波那契
**********/

#include 
#include 
#include 
#include 

#define gc getchar

using namespace std;

inline void rd(int &a)
{
    int r = 0, f = 1;
    char c = gc();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = gc();
    }
    while ('0' <= c && c <= '9')
    {
        r = (r << 3) + (r << 1) + (c - '0');
        c = gc();
    }
    a = r * f;
}

int n, m, a, x, f1[25], f2[25];

int main()
{
    rd(a), rd(n), rd(m), rd(x);
    f1[2] = 1, f1[3] = 2;
    for (int i = 4; i < n; i ++ )
    {
        f1[i] = f1[i - 1] + f1[i - 2] - 1;
        f2[i] = f2[i - 1] + f2[i - 2] + 1;
    }
    int t = (m - a * f1[n - 1]) / f2[n - 1];
    printf("%d\n", a * f1[x] + t * f2[x]);
    return 0;
}

二二年4.8

luogu P1239 计数器

题目

  • 标签 ：递推

  • 题意 ：\(1\) 到 \(n\) 中 \(0\) ~ \(9\) 出现的次数。

  • 数据范围 ：\(1?n?10^9\)。

  • 做法 ： 递推，具体见代码。

分数 ： \(100\)。

code 
/**********
2022.4.8
kroyosh
luogu P1239 计数器
递推
**********/
#include 
#include 
#include 
#include 

#define ll long long 
#define gc getchar

using namespace std;

inline void rd(ll &a)
{
    ll r = 0;
    int f = 1;
    char c = gc();
    while ('0' > c || c > '9')
    {
        if (c == '-') f = -1;
        c = gc();
    }
    while ('0' <= c && c <= '9')
    {
        r = (r << 3) + (r << 1) + (c - '0');
        c = gc();
    }
    a = r * f;
}

ll a;

ll get(ll n)
{
    ll res = 0;
    while (n) res ++ ,n /= 10;
    return res;
}

ll qmi(ll a, ll k)
{
    ll res = 1;
    while (k)
    {
        if (k & 1) res *= a;
        a *= a;
        k >>= 1;
    }
    return res;
}

ll count(int n, int i)
{
    ll res = 0, cnt = get(n);
    for (int j = 1; j <= cnt; j ++ )
    {
        ll p = qmi(10, cnt - j), l = n / p / 10, r = n % p, dc = n / p % 10;
        if (i) res += l * p;
        else res += (l - 1) * p;
        if (i == dc) res += r + 1;
        if (i < dc) res += p;
    }
    return res;
}

int main()
{
    rd(a);
    for (int i = 0; i <= 9; i ++ )
    printf("%d\n", count(a, i));
    return 0;
}

二二年4.10

NOIP2006 普及组 数列

题目

  • 标签 ：数学， 进制

  • 题意 ：把所有 \(k\) 的次方幂及所有有限个互不相等的 \(k\) 的次方幂之和构成一个递增的序列，请你求出这个序列的第 \(N\) 项的值

  • 数据范围 ： \(3?k?15,10?N?1000\)。

  • 做法 ：将 \(N\) 转化为二进制，再将其视为 \(k\) 进制数，转化为十进制数即可。

分数 ： \(100\)。

code 
/**********
2022.4.10
kroyosh
luogu P1062 [NOIP2006 普及组] 数列
数学， 进制
**********/
#include 
#include 
#include 
#include 

#define ll long long
#define gc getchar

using namespace std;

inline void rd(int &a)
{
    int r = 0, f = 1;
    char c = gc();
    while ('0' > c || c > '9')
    {
        if (c == '-') f = -1;
        c = gc();
    }
    while ('0' <= c && c <= '9')
    {
        r = (r << 3) + (r << 1) + (c - '0');
        c = gc();
    }
    a = r * f;
}

int k, n;
int num[15], m;
ll ans;

ll qmi(int a, int k)
{
    ll res = 1;
    while (k)
    {
        if (k & 1) res *= a;
        a *= a;
        k >>= 1;
    }
    return res;
}

int main()
{
    rd(k), rd(n);
    while (n)
    {
        num[ ++ m] = (n & 1);
        n >>= 1;
    }
    for (int i = 0; i <= m; i ++ )
        ans += num[i + 1] * qmi(k, i);
    printf("%lld\n", ans);
    return 0;
}

二二年4.11

luogu P8278 「MCOI-08」【A】Fill In

题目

  • 标签 ：构造

  • 题意 ：给定一个 \(a\) 的前缀和数组 \(p\)，有些位置的数未知， 求满足限制的数组 \(a\)。

  • 数据范围 ：\(1?n,∑n?10^5\)。

  • 做法 ： 前一个已知前缀和的位置 \(l\) ，当前已知前缀和的位置 \(p\) ，两数差 \(s\)， \(a[l + 1]\) 到 \(a[p]\) 的值 \(t\) 为 \(s÷两数位置差\) ，如果 \(a[l + 1]\) 到 \(a[p]\) 每个位置都填上 \(t\) 后 \(s\) 有余， 将其加在 \(a[p]\) 上。

分数 ： \(100\)。

code 
/**********
2022.4.10
kroyosh
luogu P8278 「MCOI-08」【A】Fill In
构造
**********/
#include 
#include 
#include 
#include 

#define gc getchar

using namespace std;

inline void rd(int &a)
{
    int r = 0, f = 1;
    char c = gc();
    while (c < '0' || '9' < c)
    {
        if (c == '-') f = -1;
        c = gc();
    }
    while ('0' <= c && c <= '9')
    {
        r = (r << 3) + (r << 1) + (c - '0');
        c = gc();
    }
    a = r * f;
}

const int N = 1e5 + 10;

int T, n, p[N];
int m, q[N], a[N];

int main()
{
    rd(T);
    while (T -- )
    {
        rd(n);
        m = 0;
        for (int i = 1; i <= n; i ++ )
        {
            rd(p[i]);
            if (~p[i]) q[ ++ m] = i;
        }

        for (int i = 1; i <= m; i ++ )
        {
            int t = (p[q[i]] - p[q[i - 1]]) / (q[i] - q[i - 1]), s = p[q[i]] - p[q[i - 1]];
            for (int j = q[i - 1] + 1; j <= q[i]; j ++ )
            a[j] = t, s -= t;
            if (s) a[q[i]] += s;
        }
        for (int i = q[m] + 1; i <= n; i ++ )
            a[i] = 1;
        for (int i = 1; i <= n; i ++ )
            printf("%d ", a[i]);
        puts("");
    }
    return 0;
}

二二年4.12

luogu P3017 [USACO11MAR]Brownie Slicing G

题目

  • 标签 ： 贪心。
  • 题意 ：求 \(S\) 的一个子集 \(s\) 的最大值减平均值的最大值。
  • 数据范围 ：\(1?Q?5×10^5,1?x?10^9\)。
  • 做法 ： 贪心。对于一个数 \(x\) ，如果 \(x\) > \(maxx\) ,或者 \(x\) < \(avgs\), 则将 \(x\) 加入子集 \(s\) 中。

分数 ： \(100\)。

code 
/**********
2022.4.16
kroyosh
codeforces 939E Maximize!
**********/
#include 
#include 
#include 
#include 
#include 

#define gc getchar
#define db double
#define int long long

using namespace std;

inline void rd(int &a)
{
    int r = 0, f = 1;
    char c = gc();
    while (c < '0' || '9' < c)
    {
        if (c == '-') f = -1;
        c = gc();
    }
    while ('0' <= c &&c <= '9')
    {
        r = (r << 3) + (r << 1) + (c - '0');
        c = gc();
    }
    a = r * f;
}

const int N = 5e5 + 10;

int maxx, az, am;
multiset S;

int com(int x)
{
    return x * am < az;
}

signed main()
{
    int T, op, x;
    rd(T);
    am = 1;
    while (T -- )
    {
        rd(op);
        if (op == 1)
        {
            rd(x);
            S.insert(x);
            if (x > maxx)
            {
                az = az - maxx + x;
                maxx = x;
            }
            while(S.size() && com(*S.begin()))
            az += *S.begin(), am ++, S.erase(S.begin());
        }
        else printf("%.14lf\n", 1.0 * maxx - (1.0 * az / am));
    }
    return 0;
}
题

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Windows cmd 启动 tomcat 中文乱码问题

微积分(A)随缘一题[7]

tensorboard图表显示不全的问题

Ubuntu 断网问题解决

struts2升级至2.5.26遇到的问题

OracleDataReader.Read()耗时过高问题的解决办法

recokemq整合问题

执行上下文与执行上下文栈：变量声明提升与函数声明提升 执行上下文 执行上下文栈 测试

JAVA List<Object[]>取值问题

修复 layer插件 在 bootstrap 4.x 下按钮颜色问题

Scss支持多主题切换的方案实现

标签