Contest15 首A代码

contest

A hesorchen

//https://blog.csdn.net/hesorchen
// #include <bits/stdc++.h>
#include<iostream>
using namespace std;
#define ll long long
#define mem(a, b) memset(a, b, sizeof(a))
#define lowbit(a) (a & (-a))
#define mod 1000000007
#define endl "\n"
int main()
{
    ll a, b, c;
    cin >> a >> b >> c;
    cout << c / min(a, b)<<endl;
    return 0;
}

B hesorchen

//https://blog.csdn.net/hesorchen
// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define mem(a, b) memset(a, b, sizeof(a))
#define lowbit(a) (a & (-a))
#define mod 1000000007
#define endl "\n"
int main()
{
    ll n, minn = 1000000009, a;
    cin >> n;
    ll ans = 0;
    while (n--)
    {
        cin >> a;
        if (a <= minn)
            ans++;
        minn = min(minn, a);
    }
    cout << ans << endl;
    return 0;
}

C 541907190117

/**************************************************************************************************
O[OOO@@OO@@O@@O@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@O^...=@@@@@@@@@@@@@@O[.........=@@@@@@@@@@@@
.....[OOOOOOOOOOOOO@@@@@@@@@@@OOOOOOOOO@@OOOOOOOOOOOOO[..../OOOO@@@@@@/\O/............OOOOOOOOOOOOO
^........,\OOOOOOOO@@@@@@@@@@OOOOOOOOOOO[[....................,[OOOO`.........`./O...=OOOOOOOOOOOOO
O`....].........,\O@@@@@@@@@@OOOOOO/........................................,O@@@^.../OOOOOOOOOOOOO
OO....O@@\`.........,\@@@@@@@OOO[..........................................=@@@@@`..,OOOOOOOOOOOOOO
@@\...=@@@@@\...........,\@@@`............................................*`=@@@/...OOOOOOOOOOOOOOO
@@@O...=@@@^,`..............................................................=/@@...=OOOOOOOOOOOOOOO
@@@@\...O@OO`.................................................................\^...OOOOOOOOOOOOOOOO
@@@@@\...\@`......................................................................OOOOOOOOOOOOOOOOO
@@@@@@\.../......................................................................=OOOOOOOOOOOOOOOOO
OOOOOOO.......................... ................................................\@@OOOOOOOOOOOOOO
@@@@@@@@@`................................=^...................^...................=@@@@@@@@@@@@@@@
@@@@@@@@@@...*.............................*...................*....................O@@@@@@@@@@@@@@
OOOOOOOOO.....**............. .......................................................@@@@@@@@@@@@@@
OOOOOOOOOOO`..****..........................*................................. ......=@@@@@@@@@@@@@
OOOOOOOOOOOOOO.*****,............................. ...................................O@@@@@@@@@@@@
@@@@@@@@@@@@O...***./..*..............................................................O@@@@@@@@@@@@
@@@@@@@@@@@@..........,..........,`........................................*......*..*=@@@@@@@@@@@@
@@@@@@@@@@@^.........*.,`......,@@@@@@@@@@@@@@@@@@@\]]]`...,]]@@@@@@@@@[\@@/@@@@@@O....O@@@@@@@@@@@
@@@@@@@@@@O.,`.......=.........,@@@@O[..,/OOOOO\....@@@@@@@@@@`.OOOOOOOO.,....=@@@O....\@@@@@@@@@@@
@@@@@@@@@@`=@^...................\@@[..=/[,\`..\.....@@`...@@@..,]....,/.......@@^[^...=@@@@@@@@@@@
@@@@@@@@@@=@@^....................@@....[\`..][.....@@`.....\@\....,[.........,@@....=.=@@@@@@@@@@@
@@@@@@@@@\@@O..........^..........,@^.............]@/........,@@`.............//....*...@@@@@@@@@@@
@@@@@@@@@@@@^.........*,.`..........@@\]]]..,]]/@/[............,\@@\]]`..,]]/@/.......*.\O@@@@@@@@@
@@@@@@@@@@@@.....**...=*,*..................................................*`........*.=@@@@@@@@@@
@@@@@@@@@@@O......*...,**=^...........................................................*..O@@@@@@@@@
OOOOOOOOOOO^......*...*`**,.. .........................................,.................OO@@@@@@@@
OOOOOOOOOOO^..........*^***,..  .....................................**..................OO@@@@@@@@
@@@@@@@OO@@..*.........^****\.........**\].......................]*.....................*OO@@@@@@@@
@@@@@@OO@@^......*.....=\***=`.........*=^**,[]`.............``.**...**............/`...=@@@@@@@@@@
@@@@@OO@@O^..,..**...*..=****o..........*=*********[,]...]o*.....*******.............../OO@@@@@@@@@
@@@@OO@@OO\..=/..**...*..o`**,^*........*=***************,/**...*******..........*..../@@@@@@@@@@@@
@@@OO@@@OO@^..O^.....@@@O/O],[\]]......../@@@\`*******]@@@@`*..***,//`]/@@@^....*...,/@@@@@@@@@@@@@
@@OO@@@OO@O\...O.....,@@@@@@@@@@@@`...@@/@@@@@@@`.**,@@@@@@@@@@@O]/@@@@@@@@.........=@@@@@@@@@@@@@@
**************************************************************************************************/
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define endl '\n'
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define mst(a) memset(a, 0, sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define _test printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n")
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> P2;
const double pi = acos(-1.0);
const double eps = 1e-7;
const ll MOD =  1000000007LL;
const int INF = 0x3f3f3f3f;
const int _NAN = -0x3f3f3f3f;
const double EULC = 0.5772156649015328; 
const int NIL = -1;
template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
const int maxn = 1e5+10;
ll arr[maxn] = {-9};
int main(void) {
    for (int i = 1, t, t2; i<maxn; ++i) {
        t = i, t2 = i;
        while(t) {
            t2 += t%10;
            t /= 10;
        }
        if (t2 <= 100000 && !arr[t2])
            arr[t2] = i;
    }
    int t;
    scanf("%d", &t);
    while(t--) {
        int num;
        scanf("%d", &num);
        printf("%lld\n", arr[num]);
    }
    return 0;
}

D lnkkerst

#include <iostream>
using namespace std;
#define int long long
int l, r, a, b;
int gcd(int x, int y) {
    return !y ? x : gcd(y, x % y);
}
int lcm(int x, int y) {
    return x * y / gcd(x, y);
}
signed main() {
    cin >> l >> r >> a >> b;
    int t = lcm(a, b);
    int ans = r - l + 1;
    ans -= (r) / a - (l - 1) / a;
    ans -= (r) / b - (l - 1) / b;
    ans += (r) / t - (l - 1) / t;
    cout << ans;
    return 0;
}

E hesorchen

//https://blog.csdn.net/hesorchen
// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define mem(a, b) memset(a, b, sizeof(a))
#define lowbit(a) (a & (-a))
#define mod 1000000007
#define endl "\n"
ll zuhe(ll n, ll m)
{
    ll a = 1, b = 1;
    for (int i = n; i > n - m; i--)
        a *= i;
    for (int i = 1; i <= m; i++)
        b *= i;
    return a / b;
}
ll p[100] = {1, 5, 17, 49, 129, 321, 769, 1793, 4097, 9217, 20481, 45057, 98305, 212993, 458753, 983041, 2097153, 4456449, 9437185, 19919791, 40934240, 85635360, 162200853, 329314625, 434219937, 1001996852, 1649979779, 3139896570, 2514876211, 6265438914, 9491293469, 13540317595, 20548233969, 33446368715, 15048064581, 40189067607, 40811498685, 59399120025, 96275183197, 129030690842, 168010512548, 262738143190, -101495838273, 18277894373, 197031734518, 401760972831, 226207130411, 540955206077, 548189037620, 665107065036, 947089322773, 950871050259, 1188398367837, 1681173095220, 2091832350787, 2491879393861, 2921490344108};
int main()
{
    ll n;
    while (cin >> n)
    {
        n -= 1;
        int temp = n;
        ll t = 1;
        while (temp--)
        {
            t *= 2;
        }
        cout << 1 + (n - 1) * t << endl;
    }
    //1+（n-1)*2^n
    return 0;
}

F Ruikertql

#include<stdio.h>
int main()
{
    int a,b,m[50000],n[50000],k=0,begin,end=0,kind;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        k=0;
        printf("%d/%d = %d.",a,b,a/b);
        if(a%b)
        {
            a=a%b*10;
            int flag=0;
            while(flag==0)
            {
                k++;
                m[k]=a/b;
                n[k]=a%b;
                a-=m[k]*b;
                if(n[k]==0)
                {
                    begin=k;end=k;
                    kind=2;flag=1;
                    break;
                }
                a*=10;
                for(int i=1;i<k;i++)
                {
                    if(m[i]==m[k]&&n[i]==n[k])
                    {
                        begin=i;end=k-1;
                        flag=1;kind=1;
                        break;
                    }
                }
            }
        }
        else
        {
            begin=end=0;
            kind=2;
        }
        if(kind==2)
        {
            for(int i=1;i<=end;i++)printf("%d",m[i]);
            printf("(0)\n");
        }
        else
        {
            for(int i=1;i<begin;i++)printf("%d",m[i]);
            printf("(");
            if(end<=50)for(int i=begin;i<=end;i++)printf("%d",m[i]);
            else
            {
                for(int i=begin;i<=50;i++)printf("%d",m[i]);
                printf("...");
            }
            printf(")\n");
        }
        printf("   %d = number of digits in repeating cycle\n\n",end-begin+1);
    }
}

G lnkkerst

#include <iostream>
using namespace std;
int n, m;
int f[110][110], a[110][110];
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int solve(int x, int y) {
    if(f[x][y] > 1) return f[x][y];
    for(int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] < a[x][y])
            f[x][y] = max(f[x][y], solve(nx, ny) + 1);
    }
    return f[x][y];
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            f[i][j] = 1, cin >> a[i][j];
    int ans = -1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            ans = max(solve(i, j), ans);
    cout << ans;
    return 0;
}

H 1070856563

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double eps=1e-7;
const int N=250005;
const ll mod=1000000007;
const int maxn = 1e5 + 5;
ll t[maxn];
ll a[maxn];
void calJc(ll mod)
{
    t[0] = t[1] = 1;
    for (ll i = 2; i < maxn; i++)
    t[i]=t[i - 1]*i%mod;
}
ll pow(ll a,ll n,ll p)
{
    ll ans = 1;
    while(n)
    {
        if(n&1) ans=ans*a%p;
        a = a*a%p;
        n >>= 1;
    }
    return ans;
}
ll niYuan(ll a,ll b)
{
    return pow(a,b - 2,b);
}
ll C(ll a, ll b, ll mod)
{
    return t[a]*niYuan(t[b],mod)%mod*niYuan(t[a - b],mod)%mod;
}
int main()
{
    calJc(mod);
    int x,y;
    scanf("%d%d",&x,&y);
    int mx=min(x,y);
    ll ans=0;
    while(mx>0)
    {
        int xx=x-mx,yy=y-mx;
        ans=(ans+C(mx+xx-1,mx-1,mod)%mod*C(mx+yy-1,mx-1,mod)%mod)%mod;
        mx--;
    }
    printf("%d\n",ans);
    return 0;
}

I lnkkerst

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int MOD = (int)1e9 + 7;
int n = 2;
struct Mat {
    int m[10][10];
    int* operator[] (const int x) {
        return m[x];
    }
    Mat() {
        memset(m, 0, sizeof(m));
    }
};
int read() {
    int ret, f = 1;
    char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
    for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
    return ret * f;
}
void print(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
int mod(int x) {
    return (x % MOD + MOD) % MOD;
}
Mat mul(Mat a, Mat b) {
    Mat ret;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            for(int k = 1; k <= n; ++k)
                ret[i][j] = mod(ret[i][j] + mod(a[i][k]) * mod(b[k][j]));
    return ret;
}
signed main() {
    int f1 = read(), f2 = read(), x = read();
    if(x == 1) {
        print(mod(f1));
        return 0;
    } 
    if(x == 2) {
        print(mod(f2));
        return 0;
    }
    Mat ans, base;
    ans[1][1] = f2, ans[1][2] = f1;
    base[1][1] = 1, base[2][1] = -1, base[1][2] = 1;
    x = max(x - 2, 0ll);
    while(x) {
        if(x & 1) ans = mul(ans, base);
        base = mul(base, base);
        x >>= 1;
    }
    print(mod(ans[1][1]));
    return 0;
}

J lnkkerst

#include <cstdio>
#include <cstring>
int x, t;
char str[200010];
void solve(int len, char s[]) {
    for(int i = 1; i <= len; ++i) s[len + i] = s[i];
    int i = 1, j = 2;
    while(i <= len && j <= len) {
        int k = 0;
        while(k < len && s[i + k] == s[j + k]) ++k;
        if(k == len) break;
        if(s[i + k] > s[j + k]) i += k + 1, (i == j) && ++i;
        else j += k + 1, (i == j) && ++j;
    }
    printf("%d\n", (i < j ? i : j) - 1);
    return ;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%s", &x, str + 1);
        solve(x, str);
    }
    return 0;
}

K Ruikertql

#include<stdio.h>
#include<math.h>
int a[85][85],b[85][85];
bool dp[82][82][25445];  //一共有80*159*2=25440种取值，从-12720~12720 
int main()
{
    int m,n,derta,max,min;
    scanf("%d%d",&m,&n);
    for(int i=0;i<m;i++)for(int j=0;j<n;j++)scanf("%d",&a[i][j]);
    for(int i=0;i<m;i++)for(int j=0;j<n;j++)scanf("%d",&b[i][j]);
    derta=b[0][0]-a[0][0];
    max=12720+fabs(derta);
    min=12720-fabs(derta);
    dp[0][0][derta+12720]=true;
    dp[0][0][-derta+12720]=true;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int k=(min<80?0:min-80);k<=(max>25366?25440:max+80);k++)
            {
                if(j>0)if(dp[i][j-1][k-(b[i][j]-a[i][j])])dp[i][j][k]=true;
                if(i>0)if(dp[i-1][j][k-(b[i][j]-a[i][j])])dp[i][j][k]=true;
                if(j>0)if(dp[i][j-1][k-(a[i][j]-b[i][j])])dp[i][j][k]=true;
                if(i>0)if(dp[i-1][j][k-(a[i][j]-b[i][j])])dp[i][j][k]=true;
                if(dp[i][j][k]==true&&k<min)min=k;
                if(dp[i][j][k]==true&&k>max)max=k;
            }
        }
    }
    int ans=25441,temp;
    for(int i=0;i<25441;i++)
    {
        if(dp[m-1][n-1][i]==true)if(fabs(i-12720)<ans)ans=fabs(i-12720);
        if(i>12720&&i>ans)break;
    }
    printf("%d\n",ans);
}

L 6109118071

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100000 + 5;
int a[N], b[N], rt[N * 20], ls[N * 20], rs[N * 20], sum[N * 20];
int n, k, tot, sz, ql, qr, x, q;
void Build(int& o, int l, int r){
    o = ++ tot;
    sum[o] = 0;
    if(l == r) return;
    int m = (l + r) >> 1;
    Build(ls[o], l, m);
    Build(rs[o], m + 1, r);
}
void update(int& o, int l, int r, int last, int p){
    o = ++ tot;
    ls[o] = ls[last];
    rs[o] = rs[last];
    sum[o] = sum[last] + 1;
    if(l == r) return;
    int m = (l + r) >> 1;
    if(p <= m)  update(ls[o], l, m, ls[last], p);
    else update(rs[o], m + 1, r, rs[last], p);
}
int query(int ss, int tt, int l, int r, int k){
    if(l == r) return l;
    int m = (l + r) >> 1;
    int cnt = sum[ls[tt]] - sum[ls[ss]];
    if(k <= cnt) return query(ls[ss], ls[tt], l, m, k);
    else return query(rs[ss], rs[tt], m + 1, r, k - cnt);
}
void work(){
    scanf("%d%d%d", &ql, &qr, &x);
    int ans = query(rt[ql - 1], rt[qr], 1, sz, x); 
    printf("%d\n", b[ans]);
}
int main(){
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) scanf("%d", a + i), b[i] = a[i];
    sort(b + 1, b + n + 1);
    sz = unique(b + 1, b + n + 1) - (b + 1);
    tot = 0;
    Build(rt[0],1, sz);
    //for(int i = 0; i <= 4 * n; i ++)printf("%d,rt =  %d,ls =  %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]);
    for(int i = 1; i <= n; i++)a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b;
    for(int i = 1; i <= n; i++)update(rt[i], 1, sz, rt[i - 1], a[i]);
    //for(int i = 0; i <= 5 * n; i++)printf("%d,rt =  %d,ls =  %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]);
    while(q--)work();
    return 0;
}