Day1

AcWing 1843. 圆形牛棚

数据范围很小直接枚举起点就好

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

const int N = 1005;
int n , a[N] , res = 0x7f7f7f7f;

int main()
{
    cin >> n;
    for (int i = 1; i <= n ; i ++ )
        cin >> a[i];
    for( auto i = 1 , sum = 0 ; i <= n ; sum = 0 , i ++ )
    {
        for( int j = i + 1 ; j <= n ; j ++ )
            sum += a[j] * (j-i);
        for(  int j = 1 ; j < i ; j ++ )
            sum += a[j] * ( n - i + j );
        res = min( res , sum );
    }
    cout << res << endl;
}

AcWing 1855.愤怒的奶牛

数据很小就暴力做，每次枚举一点把他放到set中
只要set没有空就把取出两侧的点并算出新的爆炸范围，然后判断剩下的点是否在爆炸范围中

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

const int N = 105;
int  n , res;
set<int> a , b , c ;

int main()
{
    cin >> n;
    for( x ;  n ; n -- )
    {
        cin >> x;
        a.insert(x);
    }

    for( auto it : a )
    {
        b = a , b.erase(it) , c.insert(it);
        int t = 1 , cnt = 1;
        while( c.size() )
        {
            int l = (*c.begin() )-t , r = (*c.rbegin())+t;
            t ++ , c.clear();
            for( auto ct : b )
                if(  ct >= l && ct <= r ) c.insert(ct);
            cnt += c.size();
            for( auto ct : c ) b.erase(ct);
        }
        res = max( res , cnt );
    }

    cout << res << endl;
}

AcWing 1801. 蹄子剪刀布

可以任意规定1,2,3的获胜情况，然后把所有的映射情况枚举一遍就好

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N = 105;
int  n , a[N] , b[N] , res;
int p[6][4] = {
        {0,1,2,3},
        {0,1,3,2},
        {0,2,1,3},
        {0,2,3,1},
        {0,3,1,2},
        {0,3,2,1},
};

inline bool judge( int x , int y )
{
    if( x == 1 && y == 2 ) return 1;
    if( x == 2 && y == 3 ) return 1;
    if( x == 3 && y == 1 ) return 1;
    return 0;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    for (int j = 0 , cnt = 0 ; j < 6 ; cnt = 0 ,  j++)
    {
        for (int i = 1; i <= n; i++ )
           if( judge(p[j][a[i]] , p[j][b[i]] ) ) cnt ++;
        res = max( res , cnt );
    }
    cout << res << endl;
}

AcWing 3347. 菊花链

做一遍前缀和，在枚举一遍端点，算出平均值，在遍历一边就行

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 105;
int n , p[N] , res;

int main()
{
    cin >> n;
    for( int i = 1 ; i <= n ; i ++ )
    {
        cin >> p[i];
        p[i] += p[i-1];
    }
    for( int i = 1 , m ; i <= n ; i ++ )
        for( int j = i ; j <= n ; j ++ )
        {
            if( ( p[j] - p[i-1] ) % (j-i+1) ) continue;
            m = ( p[j] - p[i-1] ) / (j-i+1);
            for( int k = i ; k <= j ; k ++ )
            {
                if(p[k] - p[k-1] == m )
                {
                    res ++;
                    break;
                }
                
            }
        }
            ;
    cout << res << endl;
    return 0;
}

AcWing 1826. 农田缩减

我们可以通过枚举每个点来确定边界，如果去掉的本身不在别边界上就不会对答案造成影响，所以我们可以先预处理出当前的边界

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

#define PII pair<int,int>

const int inf = 0x7f7f7f7f , N = 5e4+5;
int n ,x[N] , y[N] , a[N] , b[N] , res = inf;

int main()
{
	cin >> n;
	for( int i = 1 ; i <= n ; i ++ )
	{
		cin >> x[i] >> y[i];
		a[i] = x[i] , b[i] = y[i];
	}
	sort( a+1 , a +1+n ) , sort( b+1 , b+1+n );
	for( int i = 1 ; i <= n ; i ++ )
	{
		int x1 , x2 , y1 , y2;
		x1 = x[i] == a[1] ? a[2] : a[1];
		x2 = x[i] == a[n] ? a[n-1] : a[n];
		y1 = y[i] == b[1] ? b[2] : b[1];
		y2 = y[i] == b[n] ? b[n-1] : b[n];
		res = min( res ,  ( x2-x1)*(y2-y1) );
	}
	cout << res << endl;
}

AcWing 1813. 方块游戏

贪心的确定每一张卡牌的每个字母可能用到的最大值

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

const int N = 30;
int n , p[N] , t1[N] , t2[N];
string s1 , s2;

int main()
{
	cin >> n;
	for( int i = 1 ; i <= n ; i ++ )
	{
		cin >> s1 >> s2;
		memset( t1 , 0 , sizeof(t1) ) , memset( t2 , 0 , sizeof(t2) );
		for( auto it : s1 ) t1[it-'a']++;
		for( auto it : s2 ) t2[it-'a']++;
		for( int i = 0 ; i < 26 ; i ++ ) p[i] += max( t1[i] , t2[i] );
	}
	for( int i = 0 ; i < 26 ; i ++ ) cout << p[i] << endl;
	return 0;
}

Day 6

2022 天梯模拟赛

A 迷子のCDケース

这道题其实不算难，就是不断的做swap就好，因为数据范围很小可以直接暴力找

#include <bits/stdc++.h>
#define F first
#define ll long long
#define S second
using namespace std;

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

const int N = 105;
int n , a[N] , m , t = 0 , b[N] ;

int main()
{
    n = read() , m = read();
    for( int i = 1 ; i <= n ; i ++ ) a[i] = i;
    for( int i = 1 , x  ; i <= m ; i ++ )
    {
        x = read();
        for( int j = 1 ; j <= n ; j ++ )
        {
            if( a[j] != x ) continue;
            swap( a[j] , a[0] );
            break;
        }
    }
    for( int i = 1 ; i <= n ; i ++ ) printf("%d\n" , a[i] );

}

B ゴールドラッシュ

挨个去max相加就行

#include <bits/stdc++.h>
#define F first
#define ll long long
#define S second
using namespace std;

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

const int N = 10;
int a[N] , b[N] , res;

int main()
{
    int n = 7;
    for( int i = 1 ; i <= n ; i ++ ) a[i] = read();
    for( int i = 1 , x ; i <= n ; i ++ ) x = read() , res += max( a[i] , x );
    cout << res << endl;
}

C 心配性な富豪、ファミリーレストランに行く。

排个序就好了

#include <bits/stdc++.h>
#define F first
#define ll long long
#define S second
using namespace std;

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

const int N = 105;
int n , a[N] ;

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <=n;i++) a[i] = read();
    sort( a+1 , a+1+n);
    for(int i=n-1;i>=1;i--)
    {
        if(a[i]!=a[i+1])
        {
            printf("%d\n",a[i]);
            return 0;
        }
    }
    return 0;
}

D Get Your Wish

其实也是很暴力的做就行，但是这道题坑点就是水滴不只有一个

#include<bits/stdc++.h>using namespace std;const int N = 105;int n , m , sx ,sy , dx , dy ;char c;bool f[N][N] , v[N][N];inline int read(){    int x = 0 , ch = getchar();    while( ch < '0' || ch > '9' ) ch = getchar();    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();    return x;}int main(){    n = read() , m = read(); cin >> c;	if( c == '>' ) dx = 0 , dy = 1;	else if( c == '<' ) dx = 0 , dy = -1;	else if( c == '^' ) dx = -1 , dy = 0;	else dx = 1 , dy = 0;	for( int i = 1 ; i <= n ; i ++ )	{		for( int j = 1 ; j <= m ; j ++ )		{			c = getchar();			while( c != '.' && c != 'x' && c != 'o' ) c = getchar();			if( c == 'o' )			{				sx = i , sy = j;				while( sx >= 1 && sy >= 1 && sx <= n && sy <= m )				{					v[sx][sy] = 1;					sx += dx , sy +=dy;				}			}			else if( c == 'x' ) f[i][j] = 1;		}	}	for( int i = 1 ; i <= n ; i ++ )		for( int j = 1 ; j <= m ; j ++ )			if( f[i][j] && v[i][j] ) printf("GG\n") , exit(0);	printf("OK\n");    return 0;}

E 双生独白

这里牵扯到问提就是进制转换的问提了，Python自带丰富的进制转换问题，这里牵扯的问题就是16进制字符串转换成十进制的数字

n = int(a,16)这样就做好了，还有就是输出十六进制虽然可以转化成字符串在输出实际上可以直接进行格式化输出就好了print("{:02X}".format(n))

n = input()R = n[1:3]G = n[3:5]B = n[5:7]r = 255-int(R,16)b = 255-int(B,16)g = 255-int(G,16)print("#{:02X}{:02X}{:02X}".format(r,g,b) );

F Switches

这里因为灯和开关的数量都比较少，所以就直接用dfs枚举出所有的组合情况，然后判断就行

#include<bits/stdc++.h>using namespace std;const int N = 15;int n , m , a[N] , p[N] , res;vector<int>s[N];inline int read(){    int x = 0 , ch = getchar();    while( ch < '0' || ch > '9' ) ch = getchar();    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();    return x;}bool check(){	for( int i = 1 ; i <= m ; i ++ )		if( p[i] & 1 ) return 0;	return 1;}void dfs( int step ){	if( step > n )	{		if(check()) res ++;		return ;	}	dfs( step + 1 );	for( auto it : s[step] ) p[it]++;	dfs( step + 1 );	for( auto it : s[step] ) p[it]--;}int main(){	n = read() , m = read();	for( int i = 1 , x , k  ; i <= m ; i ++ )	{		k = read();		for( ; k ; k -- ) x = read() , s[x].push_back(i);	}	for( int i = 1 ; i <= m ; i ++ ) p[i] = read();	dfs( 1 );	cout << res << endl;    return 0;}

G 合并果子

合并果子就是做一个贪心就好了，直接把所有的果子丢进小根堆，然后每次取出最小的两个合并再丢回去

#include<bits/stdc++.h>using namespace std;int n , res;priority_queue<int , vector<int> , greater<int> >q;inline int read(){    int x = 0 , ch = getchar();    while( ch < '0' || ch > '9' ) ch = getchar();    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();    return x;}int main(){    n = read();    for(int i=1 , x ; i<=n ; i++ )		x = read() , q.push(x);	int a , b;	while( q.size() > 1 )	{		a = q.top() , q.pop();		b = q.top() , q.pop();		res += a + b ;		q.push( a + b );	}	cout << res << endl;    return 0;}

H 洛谷团队训练VS传统团队训练

对于洛谷训练比较简单可以直接用公式计算，对于传统的训练就是做一遍统计先统计每个人需要更新几次成绩表，同时再统计下每个人每道题提交了几次，然后对于每道题枚举一下每个人判断是在教师机快还是在学生机快就行

#include<bits/stdc++.h>#define ll long longusing namespace std;const int N = 1005;int n , m , ta , tb ,tc , td , A , H , E , R ;int sub[N][N] , sco[N][N]; //submit , scoremap<int,int> pro , stu;ll luogu , cena;inline int read(){    int x = 0 , ch = getchar();    while( ch < '0' || ch > '9' ) ch = getchar();    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();    return x;}int main(){	n = read() , m = read();	for( int i = 1 , x ; i <= n ; i ++ ) x = read() , pro[x] = i;	for( int i = 1 , x ; i <= m ; i ++ ) x = read() , stu[x] = i;	ta = read() , tb = read() , tc = read() , td = read() , A = read() , H = read() , E = read();	R = read();	luogu = (n*ta+R*tc)*100.0 / A + H , cena = n*ta;	for( int pr , st , sc ; R ; R -- )	{		pr = read() , st = read() , sc = read();		pr = pro[pr] , st = stu[st] , sub[st][pr] ++;		if( E && sc > sco[st][pr] ) sco[st][pr] = sc , cena += td;	}	for( int i = 1 ; i <= m ; i ++ )		for( int j = 1 ; j <= n ; j ++ )			cena += min( tb*sub[i][j] , ta + tc*sub[i][j] );	cout << cena << '\n' << luogu << '\n';	if( luogu < cena ) printf("Use Luogu!\n");	else printf("Forget it...\n");    return 0;}

I 「物理」平抛运动

这道题就是简单的高中物理题目，计算的时候注意一下就好

\(v_x=v\sin\theta=xt,v_y=v\cos\theta=\frac{1}{2}gt^2\)

import mathv , a = map(float ,input().split(' '))vx = v * math.sin(a)vy = v * math.cos(a)t = vy/ 10.0y = 5 * t * tx = vx * tprint(x,y)

K 车的攻击

其实车所在的位置是不重要的，重要的是车占据了几行几列，所以分别用两个数组存储每个车在哪一行那一列，然后排序去重就知道了，知道行列后答案就是\(n(r+c)-rc\)

#include<bits/stdc++.h>#define ll long longusing namespace std;const int N = 1e6+5;ll n , r , c;int k , a[N] , b[N];inline int read(){    int x = 0 , ch = getchar();    while( ch < '0' || ch > '9' ) ch = getchar();    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();    return x;}int main(){	n = read() , k = read();	for( int i = 1 ; i <= k ; i ++ )		a[i] = read() , b[i] = read();	sort( a+1 , a+1+k ) , sort( b+1 , b+1+k );	r = unique( a+1 , a+1+k ) - a-1 , c = unique( b+1 , b+1+k ) - b-1;	cout << n*(r+c) - r*c << endl;    return 0;}

L 售票

数据很小直接暴力的判断就好

#include<bits/stdc++.h>#define ll long longusing namespace std;string t[4] = { "***ABCDE",				"FGHIJKLM",				"NOPQRSTU",				"VWXYZ***"};string s[55] , cur;int n , m;bool f[30];inline int read(){    int x = 0 , ch = getchar();    while( ch < '0' || ch > '9' ) ch = getchar();    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();    return x;}int main(){	cin >> n;	for( int i = 1 ; i <= n ; i ++ ) cin >> s[i];	cin >> cur;	m = cur.size();	for( int i = 1 , fa = 1 ; i <= n ; i ++ , fa = 1 )	{		if( s[i].size() <= m ) continue; 		for( int j = 0 ; j < m ; j ++ )		{			if( cur[j] == s[i][j] ) continue;			fa = 0;			break;		}		if( fa ) f[ s[i][m]-'A' ] = 1;	}	for( int i = 0 ; i < 4 ; i ++ )	{		for( int j = 0 ; j < 8 ; j ++ )			{				if(t[i][j] == '*' ) printf("*");				else if( f[t[i][j]-'A'] ) cout << t[i][j];				else printf("*");			}		cout << "\n";	}}

N Balanced Photo G

先把所有的牛离散化一下，然后排个序，从左侧开始遍历，因为排序所以可以通过位置计算一共有多少牛比当前牛高，然后在用一个树状数组维护当左侧牛的情况就可以用计算出左侧有多少个牛比当前牛高，一减就是右侧，然后判断就好，最后把当前牛加入到树状数组中

#include<bits/stdc++.h>#define ll long long#define lowbit(x) ( x & -x )using namespace std;const int N = 1e5+5;int n , a[N] , b[N] , c[N] , res;void update( int x ){	for( int i = x ; i <= n ; i += lowbit(i) ) c[i] ++;}int get( int x ){	int ans = 0;	for( int i = x ; i ; i -= lowbit(i) ) ans += c[i];	return ans;}inline int read(){    int x = 0 , ch = getchar();    while( ch < '0' || ch > '9' ) ch = getchar();    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();    return x;}int main(){	n = read() ;	for( int i = 1 ; i <= n ; i ++ )		a[i] = b[i] = read();	sort( b + 1 , b + 1 + n );	for( int i = 1 , t , l , r ; i <= n ; i ++ )	{		t = lower_bound( b+1 , b+1+n , a[i] ) - b;		l = i - 1 - get( t-1 ) , r = n - t - l ;		if( r > l ) swap( l , r );		if( l > 2*r ) res ++;		update(t);	}	cout << res << "\n";    return 0;}

O TOU-Tour de Byteotia

首先把所有的两个点都大于k的边加到并查集中，然后开始枚举剩下的边，如果这条边加进去会形成环就不能加，计数器加一否则就是加入到并查集计数器就是答案

为什么要这么做呢？因为如果形成了环只要断掉一条边就行，至于断掉那条边无所谓，因为贡献是相同的

#include<bits/stdc++.h>#define ll long long#define lowbit(x) ( x & -x )using namespace std;const int N = 1e6+5;int n , fa[N] , cnt , m , k ;vector<pair<int,int>> e;int getfa( int x ){	if( fa[x] == x ) return x;	return fa[x] = getfa( fa[x] );}void merge( int x , int y ){	x = getfa(x) , y = getfa(y);	fa[x] = y;}inline int read(){    int x = 0 , ch = getchar();    while( ch < '0' || ch > '9' ) ch = getchar();    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();    return x;}int main(){	n = read() , m = read() , k = read();	for( int i = 1 ; i <= n ; i ++ ) fa[i] = i;	for( int i = 1 , u , v ; i <= m ; i ++ )	{		u = read() , v = read();		if( u > k && v > k ) merge(u , v);		else e.push_back({u,v});	}	for(auto [u,v] : e )	{		if( getfa(u) == getfa(v) ) cnt ++;		else merge(u , v);	}	cout << cnt << endl;    return 0;}

AtCoder Beginner Contest 239

A Horizon

按照题目要求输出就好

import mathn = float(input())print( math.sqrt(n*(12800000+n) ) )

B Integer Division

利用python整除的性质就好

import mathn = int(input())print(n//10)

C Knight Fork

先把第一个点所有的距离为根号五的点放进一个set中，在枚举第二点是否有距离为根号五的点在集合中就好

#include <bits/stdc++.h>#define F first#define ll long long#define S secondusing namespace std;const ll d[2][2] = { {1,2} , {2,1} } , t[4][2] = { {1,1} , {1,-1} , {-1,1} , {-1,-1}};ll x_1 , x_2 , y_1 ,y_2;set<pair<ll,ll>> s;int main(){	cin >> x_1  >> y_1 >> x_2 >> y_2;	for( int i = 0 ; i < 2 ; i ++ )		for( int j = 0 ; j < 4 ; j ++ )		s.insert( { x_1 + d[i][1] * t[j][1] , y_1 + d[i][0] * t[j][0] } );	for( int i = 0 ; i < 2 ; i ++ )		for( int j = 0 ; j < 4 ; j ++ )			if( s.count( { x_2 + d[i][1] * t[j][1] , y_2 + d[i][0] * t[j][0] } ) ) printf("Yes\n"), exit(0);	printf("No\n");	return 0;}

D Prime Sum Game

先跑一遍线性筛，然后分别枚举两个人出的数看时候能找到高桥说一个数，青木无论说几和都是素数

#include <bits/stdc++.h>#define F first#define ll long long#define S secondusing namespace std;const int N = 205;int n , a , b , c , d;int p[N] , cnt ;bool v[N];void prime( int x ){	for( int i = 2 ; i <= x ; i ++ )	{		if(!v[i] ) p[ ++cnt ] = i;		for( int j = 1 ; j <= cnt , i * p[j] <= x ; j ++ )		{			v[ i*p[j] ] = 1;			if( i % p[j] == 0 ) break;		}	}}int main(){	cin >> a >> b >> c >> d ;	prime( b + d );	for( int i = a , fa = 1 ; i <= b ; i ++ , fa = 1 )	{		for( int j = c ; j <= d && fa ; j ++ )			fa = v[i+j];		if(fa) printf("Takahashi\n") , exit(0);	}	printf("Aoki\n");	return 0;}