首页 > 代码库 > “玲珑杯”ACM比赛 Round #19

“玲珑杯”ACM比赛 Round #19

2024-11-11 12:13:39   202人阅读

A -- A simple math problem

Time Limit：2s Memory Limit：128MByte

Submissions：1599Solved：270

DESCRIPTION

You have a sequence anan, which satisfies:

技术分享

Now you should find the value of ?10an??10an?.

INPUT
The input includes multiple test cases. The number of test case is less than 1000. Each test case contains only one integer n(1≤n≤109)n(1≤n≤109)。
OUTPUT
For each test case, print a line of one number which means the answer.
SAMPLE INPUT
5
20
1314
SAMPLE OUTPUT
5
21
1317
这个题就是找规律啊，一个很明显的规律是每一项都有一个贡献，但是这个范需要自己找，10的话按照log是要加1结果不需要，入手点就是这里，看看哪些少加了1，每个数量级多一个，这个pow损精度，wa了好几次，主要是n==1时输出值也是1，这个才是我被坑的最严重的
以下是题解
技术分享 
#include <stdio.h>
#include <math.h>
int pow10(int i){
int ans=1;
for(int j=0;j<i;j++)
    ans*=10;
return ans;
}
int main(){
int n;
while(~scanf("%d",&n)){
int ans=n+(int)log10(n*1.0);
if(n==10)ans-=1;
for(int i=2;i<=9;i++){
    int x=pow10(i);
    if(x+1-i<n&&n<x)
        ans++;
}
printf("%d\n",ans);
}
return 0;}
B - Buildings

Time Limit：2s Memory Limit：128MByte

Submissions：699Solved：186

DESCRIPTION

There are nn buildings lined up, and the height of the ii-th house is hihi.

An inteval [l,r][l,r](l≤r)(l≤r) is harmonious if and only if max(hl,…,hr)?min(hl,…,hr)≤kmax(hl,…,hr)?min(hl,…,hr)≤k.

Now you need to calculate the number of harmonious intevals.

INPUT
The first line contains two integers n(1≤n≤2×105),k(0≤k≤109)n(1≤n≤2×105),k(0≤k≤109). The second line contains nn integers hi(1≤hi≤109)hi(1≤hi≤109).
OUTPUT
Print a line of one number which means the answer.
SAMPLE INPUT
3 1 1 2 3
SAMPLE OUTPUT
5
HINT
Harmonious intervals are: [1,1],[2,2],[3,3],[1,2],[2,3][1,1],[2,2],[3,3],[1,2],[2,3].
模板题？？？区间最大值最小值的差小于等于k的值有多少组，单调栈，RMQ都不会被卡的
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxN = 2e5+10;
int n, k, a[maxN];
LL ans;
void input() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
}
void work() {
    ans = 0;
    deque<int> mi, ma;
    int p = 0;
    for (int i = 0; i < n; ++i) {
        while (!(mi.empty() && ma.empty()) &&
                !(abs(a[i]-a[mi.front()]) <= k && abs(a[i]-a[ma.front()]) <= k)) {
            p++;
            while (!mi.empty() && mi.front() < p)
                mi.pop_front();
            while (!ma.empty() && ma.front() < p)
                ma.pop_front();
        }
        ans += i-p+1;
        while (!mi.empty() && a[mi.back()] > a[i])
            mi.pop_back();
        mi.push_back(i);
        while (!ma.empty() && a[ma.back()] < a[i])
            ma.pop_back();
        ma.push_back(i);
    }
    printf("%lld\n", ans);
}

int main() {
    input();
    work();
    return 0;
}

 

“玲珑杯”ACM比赛 Round #19


联系
我们