首页 > 其他分享 >2022河南萌新联赛第（七）场

2022河南萌新联赛第（七）场

时间：2022-08-21 22:12:23浏览次数：78  
标签：&& ch frac 萌新 int while 2022 getchar 联赛

C 机智的我

一开始有选中的概率是\(\frac{1}{n}\)，打开 k 个后的概率是\(\frac{n-1}{n}\times\frac{1}{n-k-1}\)

所以\(k=0\)没差别，\(k>0\)更换一定更好

#include<bits/stdc++.h>

using namespace std;

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


int32_t main() {
   int n = read() , k = read();
   if( k == 0 ) cout << "Whatever\n";
   else cout << "Why not\n";
   return 0;
}

H 防风台

二分答案

首先二分出答案，然后吧小于二分值的全部都选上，看看时候可以挡住所有行或列即可

#include<bits/stdc++.h>

using namespace std;



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

const int N = 1005;
int a[N][N] , r[N] , c[N] , n , m;
vector<int> ve;

bool check( int x ){
    memset( r , 0 , sizeof( r ) );
    memset( c , 0 , sizeof( c ) );
    int cnt = 0;
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= m ; j ++ ){
            if( a[i][j] <= x ){
                if( r[i] == 0 ) r[i] = 1 , cnt ++;
                if( c[j] == 0 ) c[j] = 1 , cnt ++;
            }
        }
    return cnt == n + m;
}

int32_t main() {
    n = read() , m = read();
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= m ; j ++ )
            a[i][j] = read() ;
    int l = 0 , r = 1e9 , mid , res;
    while( l <= r ){
        mid = ( l + r ) >> 1;
        if( check( mid ) )  res = mid , r = mid - 1 ;
        else l = mid + 1;
    }
    cout << res << "\n";
    return 0;
}

贪心

每一行取最小值，每一列也取最小值。然后最小值在取最大值。

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

const int N = 1005;
int a[N][N] , res = INT_MIN;

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

int32_t main() {
    int n = read() , m = read();
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= m ; j ++ )
            a[i][j] = read();
    for( int i = 1 ; i <= n ; i ++ ){
        int t = INT_MAX;
        for( int j = 1 ; j <= m ; j ++ )
            t = min( t , a[i][j] );
        res = max( res , t );
    }
    for( int j = 1 ; j <= m ; j ++ ){
        int t = INT_MAX;
        for( int i = 1 ; i <= n ; i ++ )
            t = min( t , a[i][j] );
        res = max( res , t );
    }
    cout << res << "\n";
}

G 小明不希望太简单

把字母和字母的个数放入一个大根堆中，每次拿出最多的和次多的，然后输出即可。

注意处理一些细节问题。

#include<bits/stdc++.h>

using namespace std;

string s;
int cnt[30];
priority_queue< pair<int,int> > q;

int32_t main() {
    cin >> s;
    for( char it : s )
        cnt[ it - 'a' ] ++;
    for( int i = 0 ; i < 26 ; i ++ )
        if( cnt[i] > 0 )
            q.push( { cnt[i] , 'a'+i } );

    while( q.size() ){
        auto [ v , k ] = q.top(); q.pop();
        cout << char(k) , v --;
        if( v == 0 ) continue;
        if( q.empty() ) break;

        auto [sv , sk ] = q.top(); q.pop();// 取出次多的字母
        cout << char(sk) ,  sv --;
        q.push( { v , k } );
        if( sv ) q.push( { sv , sk } );
    }
    return 0;
}

J 最短路

这道题因为询问次数很少，所以可以离线做。

按照边权从小到大加边，如果加入当前边后某个询问的两点连通，那么当前边的权值就是该询问的答案。

#include<bits/stdc++.h>

using namespace std;

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

const int N = 1e5+5;
int fa[N] , n , m , a[N] , b[N] , res[N] , q , cnt ;

struct Edge{
    int u , v , w;
    Edge( int u , int v , int w ) : u(u) , v(v) , w(w) {};
    friend bool  operator < ( Edge a , Edge b ){
        return a.w < b.w;
    }
};

vector<Edge> e;

int getFa( int x ){
    if( fa[x] == x ) return x;
    return fa[x] = getFa( fa[x] );
}

void merge( int u , int v ){
    u = getFa(u) , v = getFa(v);
    fa[v] = u;
}

int32_t main() {
    n = read() , m = read();
    for(  int u , v , w ; m ; m -- )
        u = read() , v = read() , w = read() , e.push_back( { u , v , w } );
    sort( e.begin() , e.end() );
    q = read();
    for( int i = 1 ; i <= q ; i ++ )
        a[i] = read() , b[i] = read() , res[i] = -1;
    for( int i = 1 ; i <= q ; i ++ )
        if( a[i] == b[i] ) res[i] = 0 , cnt ++;
    for( int i = 1 ; i <= n ; i ++ ) fa[i] = i;
    for( auto [ u , v , w ] : e ){
        merge( u , v );
        for( int i = 1 ; i <= q ; i ++ ){
            if( res[i] != -1 ) continue;
            if(getFa( a[i] ) == getFa(b[i] ) ) res[i] = w , cnt ++ ;
        }
        if( cnt == q ) break;
    }
    for( int i = 1 ; i <= q ; i ++ )
        cout << res[i] << '\n';
}

B 龍

首先我们可以找到所有全是零的区间，手摸就可以发现这两操作是两种

  1. 花费 a，将两个全零的区间合并
  2. 花费 b，删掉一个全零的区间

然后发现操作顺序是不会影响最终的答案的，并且每个区间的长度、端点都是无用信息罢了。

所以只要枚举一下合并多少区间就可以计算出需要删除多少区间，然后就能计算出花费，找到最小的花费就好了。

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

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

const int N = 1e3+5;
string s;

void solve(){
    int n = read() , a = read() , b = read() , x = read() , m = 0 , res = INT_MIN;
    cin >> s;
    m = (s[0] == '0');
    for( int i = 1 ; i < n ; i ++ )
        m += ( s[i] == '0' && s[i-1] == '1' );
    if( m == 0 ) {
        cout << "Yes\n" << x << "\n";
        return;
    }
    for( int i = 0 ; i < m ; i ++ )
        if( a * i + ( m - i) * b <= x ) res = max( res , x - (a * i + ( m - i) * b) );
    if( res == INT_MIN ) cout << "No\n";
    else cout << "Yes\n" << res << "\n";
    return;
}

int32_t main() {
    for( int T = read() ; T ; T -- )
        solve();
}

L ___O_o

这道题算是很简单的题目了，但是数据非常的搞人

首先两个圆的圆心是\((\frac{a}{b},\frac{1}{2b^2}),(\frac{c}{d},\frac{1}{2d^2})\)，半径是\(\frac{1}{2b^2},\frac{1}{2d^2}\)

那么外切的条件就是

\[\sqrt{(\frac{a}{b}-\frac{c}{d})^2+(\frac{1}{2b^2}-\frac{1}{2d^2})^2}=\frac{1}{2b^2}+\frac{1}{2d^2}\\ (\frac{a}{b}-\frac{c}{d})^2+(\frac{1}{2b^2}-\frac{1}{2d^2})^2=(\frac{1}{2b^2}+\frac{1}{2d^2})^2\\ (\frac{a}{b}-\frac{c}{d})^2+ (\frac{1}{2b^2})^2+(\frac{1}{2d^2})^2-\frac{1}{2b^2d^2}=(\frac{1}{2b^2})^2+(\frac{1}{2d^2})^2+\frac{1}{2b^2d^2}\\ (\frac{a}{b}-\frac{c}{d})^2=\frac{1}{b^2d^2}\\ |\frac{a}{b}-\frac{c}{d}|=\frac{1}{|bd|}\\ |ad-cb|=1 \]

内切的条件是

\[\sqrt{(\frac{a}{b}-\frac{c}{d})^2+(\frac{1}{2b^2}-\frac{1}{2d^2})}=\frac{1}{2b^2}-\frac{1}{2d^2}\\ (\frac{a}{b}-\frac{c}{d})^2+(\frac{1}{2b^2}-\frac{1}{2d^2})^2=(\frac{1}{2b^2}-\frac{1}{2d^2})^2\\ \frac{a}{b}-\frac{c}{d}=0\\ ad=bc \]

题目很坑的一点是两个完全相同的圆是不能被算作内切的，完全相同的条件就是a==c&&b==d

剩下就很简单了

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

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

const int N = 1e3+5;

void solve(){
    int a = read() , b = read() , c = read() , d = read();
    if( a == c && b == d ) cout << "NO\n";
    else if( abs( a*d - c*b ) == 1 || a * d == c * b ) cout << "YES\n";
    else cout << "NO\n";
}

int32_t main() {
    for( int T = read() ; T ; T -- )
        solve();
}

F 数对

这道题是一个蛮简单的思维题，对于任意的两个数的最高位，如果俩个数的最高位的1 在一个位置上，那么与就是 1，而异或就是0。反之，异或的最高位是 1，与的最高位是 0。

可以发现两个数对的关系仅仅与最高位的一所在的位置有关。我们可以预处理出所有数的最高位的 1 的位置。然后用前缀和维护一下区间的情况，结合组合数就可以算出结果。

值得注意的是两个 0 是复合条件的特殊情况。

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

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

const int N = 1e5+5;
int a[35][N];

int get( int x ){ // 计算最高位的 1 所在的位置
    if( x == 0 ) return 0;
    return __lg(x) + 1;
}

int32_t main() {
    int n = read() , m = read();
    for( int i = 1 , x ; i <= n ; i ++ ){
        x = read();
        for( int j = 0 ; j <= 31 ; j ++ ) a[j][i] = a[j][i-1];
        a[get(x)][i] ++;
    }
    for( int l , r , res ; m ; m -- ){
         l = read() , r = read() , res = 0;
         for( int i = 0 , t ; i <= 31 ; i ++ )//枚举区间中最高的1在i的个数
            t = a[i][r] - a[i][l-1] , res += t * ( t - 1 ) / 2;// 组合数
         cout << res << "\n";
    }
}

A 构造？

一道复杂的枚举题？

首先枚举一下序列的长度n,然后再枚举一下开头的第一个数字t，在枚举一下[2,n]中的 d 的个数i

此时满足当前条件的序列个数是\(C_{n-1}^{i}\times9^{n-i-1}\)

因为过程中会反复的用到组合数和次方，可以先递推出所有组合数和 9 点次方存在数组c[i][j],p[i]中

for( int n = l ; n <= r ; n ++ )
    for( int t = 1 ; t <= 9 ; t ++ )
        for( int i = 0 ; i <= n-1 ; i ++ )
            res += t * c[n-1][i] * p[n-i-1] * i;

但是这样忽略了一个问题就是如果t==d的情况，所以代码要订正为

for( int n = l ; n <= r ; n ++ )
    for( int t = 1 ; t <= 9 ; t ++ )
        for( int i = 0 ; i <= n-1 ; i ++ ){
            int cnt = i + ( d == t );
            int sum = c[n-1][i] * p[n-i-1];
            res += t * cnt * sum;
        }

这样的代码就是正确的，但是这样直接上交会TLE，需要优化

先来考虑d==0此时是不会出现d==t的情况的，所以对于已经确定的长度n有

\[\sum_{t=1}^9\sum_{i=0}^{n-1} t\times C_{n-1}^i\times9^{n-i-1}\times cnt=\sum_{t=1}^9t\times cnt \times \sum_{i=0}^{n-1} C_{n-1}^i\times9^{n-i-1} \\= 45cnt\sum_{i=0}^{n-1} C_{n-1}^i\times9^{n-i-1} \]

再来考虑d!=t情况，可以拆分为

\[(45-d) \sum_{i=0}^{n-1} C_{n-1}^i\times9^{n-i-1} 9 \times cnt+ d \sum_{i=0}^{n-1} C_{n-1}^i\times9^{n-i-1}\times (cnt+1)\\ =(45\times cnt + d) \sum_{i=0}^{n-1} C_{n-1}^i\times9^{n-i-1} \]

这里的 cnt和 i实际上是一个值

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

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

const int N = 105 , mod = 1e9+7;
int c[N][N] , p[N];

void solve(){
    int l = read() , r = read() , d = read() , res = 0;
    if( d == 0 ){
        for( int n = l ; n <= r ; n ++ ){
            int cnt , sum;
            for( int i = 0 ; i <= n-1 ; i ++ ){
                sum = c[n-1][i] * p[ n - i - 1 ] % mod;
                res = ( res + 45 * i % mod * sum % mod ) % mod;
            }
        }
    }
    else {
        for( int n = l ; n <= r ; n ++ ){
            int cnt , sum;
            for( int i = 0 ; i <= n-1 ; i ++ ){
                sum = c[n-1][i] * p[ n - i - 1 ] % mod;
                res = ( res + (45*i+d) % mod * sum % mod ) % mod;
            }
        }
    }
    cout << res << "\n";
}
int32_t main() {
    c[0][0] = c[1][1] = c[1][0] = 1;
    for( int i = 2 ; i <= 100 ; i ++ ){
        c[i][0] = 1;
        for( int j = 1 ; j <= i ; j ++ )
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
    }
    p[0] = 1;
    for( int i = 1 ; i <= 100 ; i ++ ) p[i] = p[i-1] * 9 % mod;

    for( int T = read() ; T ; T -- )
        solve();


}

I 计算几何

看似是一道计算几何罢了。

对于求不规则多边形的面积实际上就是定积分，但是这里并不需定积分。

把图形放在边长为\(0.01\times0.01\)的网格图中，枚举每一个格子，并判断是否在四个椭圆内即可。

赛事没出这道题属实我大傻逼了，精度没有控制好哎~~

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

double a , b , res;

void solve(){
    cin >> a >> b , res = 0;
    for (double i = -10; i <= 10; i += 0.01)
        for (double j = -10; j <= 10; j += 0.01) {
            if ((i * i) / (a * a) + (j * j) / (b * b) > 1) continue;
            if ((i * i) / (b * b) + (j * j) / (a * a) > 1) continue;
            if (i * i + j * j + i * j > a) continue;
            if (i * i + j * j - i * j > b) continue;
            res += 0.0001;
        }
    printf("%.0lf\n", res);
}
int32_t main() {
    int T ; cin >> T;
    for( ; T ; T -- )
        solve();
}

标签：&&,ch,frac,萌新,int,while,2022,getchar,联赛
From： https://www.cnblogs.com/PHarr/p/16611176.html

相关文章

  • Linq-20220817更新
    一、常用函数Where：每一项数据都会经过predicate(传入的委托lambda表达式)的测试，如果对元素执行predicate后返回值为True，则这个元素会添加到结果数组中Count：每一项数据都......
  • 2022.8.21 线程池
    11、线程池(重点)线程池Executors：3大方法、7大参数、4种拒绝策略池化技术程序的运行，本质：占用系统的资源！优化资源的使用！==>引进了一种技术池化池线程池、连接池、内......
  • 2022-08-18 MySQL常用函数
    MySQL常用函数聚合函数count：计数。count(*)≈count(1)>count(主键)count(*)：MySQL对count(*)底层优化，count(0)。count(1)count(主键)count(字段)min：最小值max：最......
  • 2022.8.21 四大函数式接口与Stream流式计算
    12、四大函数式接口（重点）   函数接口：只有一个方法的接口    @FunctionalInterface publicinterfaceRunnable{     publicabstractvoidrun(......
  • 2022.8.21 Forkjoin与异步回调
    14、Forkjoin(分支合并)什么是ForkJoinForkJoin在JDK1.7， 并行执行任务！提高效率。在大数据量中！大数据：MapReduce（把大任务拆分为小任务）Forkjoin特点：工作窃取，这里......
  • 2022.8.21 读写锁与阻塞队列
    9、读写锁   自定义的缓存，没有加锁，就会出现一个没有写入完成，另一个突然插进来的情况 packagecom.xing.rw; ​ importjava.util.HashMap; importjava.util.......
  • 2022.8.21 JUC
    1、什么是JUC1、什么是juc（学习方法：官方文档+源码）   JUC——（java.util.concurrent）是一个包名的缩写，java工具类下的一个并发功能的包。该包下存放的均为多线程相......
  • 2022-08-21 假突破立即做空，就如同突破收敛三角就做单一样，总会给你一段利润。
     同样是假突破，第二次上冲。左边完成了整个4h标准中枢，右边又形成了30分钟的笔中枢扩展。左边4h图，假突破之后，完成了4h一个全部线段中枢的上涨。最后一段是背驰段，结束了30......
  • NOI 2022 无球包亦无枪记
    NOI2022无球包亦无枪记Day-2：初才入秋，了无凉意。近午入学舍，入前与同行者合影于学舍门前。至入校，始觉报到单不见，同行者多携之，故借，草草填报于石阶上。遂利入校，惊叹贵......
  • 2022牛客多校 补赛 C Cmostp（区间结尾本质不同子串）
    多次询问求一个串的结尾在\([l,r]\)之间的本质不同子串个数。此题是求一个区间的不同元素的问题，使用扫描线的方法解决，即每次加入一个元素就将这个位置\(+1\)，这个元素上一......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99