Article From:https://www.cnblogs.com/normaldisk/p/9127340.html

Selection examination

T1
Little K has a n card in his hand, and there is a single digit number on each card. The word number is not 0 or 5. Small K draws out any Zhang from these cards (can not draw 0 pieces), row a row, thus constitute a number. Make this number as large as possible, and it can be divisible by 90.

Sample

Input:
4
5 0 5 0

Output:
0

thinking
Divisible by 90, which is divisible by 9 and 10 at the same time, is divided by 10 by at least 0, 9 divided by 9, and the number of 5 is 9.

Directly on the code:

#include<cstdio>
#include<cstring>
#include<iostream>
#define CL(X,N) memset(X, N, sizeof(X))
#define LL long long
using namespace std;
const int maxn=1e3+10;
int a[maxn], n;
int cnt5=0, cnt0=0;

inline void _init() {
    freopen("zaf.in", "r", stdin);
    freopen("zaf.out", "w", stdout);
}

int main() {
    _init();
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d", a+i);
        if(a[i]==5) cnt5++;
        if(a[i]==0) cnt0++;
    }
    if(!cnt0) {
        printf("-1");
        return 0;
    }
    int ls=cnt5/9;
    if(ls){
        for(int i=0; i<ls*9; i++) printf("5");
        for(int i=0; i<cnt0; i++) printf("0");
    } else printf("0");
    return 0;
}

 

It’s so simple, don’t want to make annotations


T2

Now there is a glass that is rectangular (W mm * x H mm mm), and now we need to cut it. There are two kinds of cutting direction, transverse and longitudinal. After each cut, several pieces of glass are divided into two smaller pieces of glass. The glass will not be moved after cutting.
Now I want to know the size of the largest piece of glass after each cut.

Sample

Input:
4 3 4
H 2
V 2
V 3
V 1

Output:
8
4
4
2

Sample explanation


For the fourth cut, the next four pieces of glass are of the same size. It’s all 2

thinking

Standard thinking:Reverse processing, if the current position x is secant, thenH[x].l represents the position of the secant on the left side of the secant.H[x].r represents the position of the secant on the right side of the secant line.H[i].val represents the length between the Secant and the left secant.So each time increases the secantAfter that, it’s equivalent to deleting the cut line.Of course, every time it is deleted as long as O (1) updates the cut line of the cut line, the answer is max (H[i].val) *max (V[i].val), I [0, w (H)], the total complexity: O (n).

Thought at that time
In order to avoid TLE, first save the operation, and mark it successively (put the upper and lower boundaries in it, ID is set to 0), and then run for and record the maximum current width and height, and output the result in turn (actually almost).

Combustible goose,What makes me muddled is that every time someone reads an operation on sort once, and runs for, there is no TLE.(It must be data too water.)

And then put the code.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define CL(X,N) memset(X, N, sizeof(X))
#define LL long long
using namespace std;
const int maxn=2e5+10;
int w, h, n;
struct cut {
    LL x;
    int id;
    cut(){}
    cut(LL _x, int _id) : x(_x), id(_id) {}
}wl[maxn], hl[maxn];

bool cmp(cut a, cut b) {
    return a.x<b.x;
}

inline void _init() {
    freopen("cut.in", "r", stdin);
    freopen("cut.out", "w", stdout);
}

int cnth=2, cntw=2;

int main() {
    _init();
    scanf("%d%d%d", &w, &h, &n);
    wl[0]=cut(0, 0);
    wl[1]=cut(w, 0);
    hl[0]=cut(0, 0);
    hl[1]=cut(h, 0); //Initializationfor(int i=1; i<=n; i++) {
        char cmd[2];
        LL x;
        scanf("%s", cmd); //Swallowed'\n'Scanf ("%d", &x);
        if(cmd[0]=='H') {
            hl[cnth++]=cut(x, i);
        } else if(cmd[0]=='V') {
            wl[cntw++]=cut(x, i);
        }
    }
    sort(wl, wl+cntw, cmp);
    sort(hl, hl+cnth, cmp);
    for(int i=1; i<=n; i++) {
        LL answ=0, ansh=0;
        LL lastw=0, lasth=0;
        for(int j=1; j<cntw; j++) {
            if(wl[j].id>i) continue;
            answ=max(answ, wl[j].x-lastw); //Maximum width of calculationLastw=wl[j].x;
        }
        for(int j=1; j<cnth; j++) {
            if(hl[j].id>i) continue;
            ansh=max(ansh, hl[j].x-lasth); //Maximum heightLasth=hl[j].x;
        }
        printf("%lld\n", answ*ansh);
    }
    return 0;
}

 This is my own code, not the standard.


T3

Xiao H is a thoughtful student. Now she is thinking about a sequence.
A sequence of {ai} length n emerges in front of her. She wants to find out an interval [L, R] (1 &lt = = L < = R < = n).
This special interval satisfies the existence of a K (L < = k &lt = R), and for any I (L &lt = = I &lt = = &lt), all can be divisible. Such a special interval [L, R] value is R – L.
Little H wants to know the maximum value of all the special intervals in the sequence, and how many such intervals? What are these intervals, respectively? You can help her.

【Input format]
The first line, an integer n.
Second lines, n integers, representing ai.

【Output format]
The first line, two integers, Num and Val, represent the number of special intervals with the greatest value and the maximum value.
Second lines num integers, and output the L. of the special interval with the greatest value in ascending order.

Sample

Input:
5
4 6 9 3 6

Output:
1 3
2

【Data range]
30%: 1 <= n <= 30 , 1 <= ai <= 32.
60%: 1 <= n <= 3000 , 1 <= ai <= 1024.
80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.
100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.

thinking

Standard thinking
30% :Violence enumerates judgment. O (n^4).
60% :The characteristic of a special interval is actually the interval minimum value equal to GCD of this interval, so the minimum and GCD of each interval are calculated by violence or recursion. For maximum value, it can be solved by two points. Complexity O (n ^ 2).
100%:On the basis of 60%, the minimum and GCD are solved by RMQ algorithm, and ST table is recommended for this problem. The maximum value is still two points. Complexity O (nlogn).

At that time:
When I see the scope of the data, I am really square, really, I felt that running a for was the limit, running two for on the TLE, GCD is more easy to TLE (also to judge the interval GCD, really dare not write),Combustible goose,I was resolute and violent. (I never thought of a better way). Finally, I wrote a O (n^2). I really resigned myself.

however,I was really happy (hahahaha…). I was really happy

And then the code:

#include<cstdio>
#include<cstring>
#include<iostream>
#define CL(X,N) memset(X, N, sizeof(X))
#define LL long long
using namespace std;
const int maxn=5e5+10;
int n;
int a[maxn];
int l[maxn]={0}, maxlen=0, num=0;
int vis[maxn];

inline void _init() {
    freopen("pair.in", "r", stdin);
    freopen("pair.out", "w", stdout);
}

int main() {
    //_init();
    CL(vis, -1);
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%d", a+i);
    }
    for(int i=1; i<=n; i++) {
        int ll=i, rr=i;
        while(ll>1 && !(a[ll-1]%a[i])) ll--;
        while(rr<n && !(a[rr+1]%a[i])) rr++;
        if(rr-ll>maxlen) {
            num=0;
            maxlen=rr-ll;
        }
        if(rr-ll==maxlen && vis[ll]!=maxlen) {
            l[num++]=ll;
            vis[ll]=maxlen;
        }
    }
    printf("%d %d\n", num, maxlen);
    for(int i=0; i<num; i++) printf("%d ", l[i]);
    return 0;
}

The title is here first

There is another thing,inlineAfter the inline function is required to return value, such as void, do not know for Mao _init () before adding void in my local can also be compiled, the final submission failed to compile, I scared… To be allowed to change back, or got a point.

This amazing local is really fascinated by it. (I wonder if anyone is like me).

Link of this Article: Problem solving report (18.06.02)

Leave a Reply

Your email address will not be published. Required fields are marked *