Day1,2
22牛客寒假训练营1
E 炸鸡块君的高中回忆
因为不论怎么操作，前面的几次最多带入m-1，最后一次最多可以带入m
所以我们就能得到一个式子\(k(m-1)+m\ge n\)，化简这个式子就能得到\(k\ge \frac{n-m}{m-1}\)
所以答案就是\(2k+1\)次，然后只需解这个不等式即可
#include<bits/stdc++.h>
using namespace std;
int n , m , res ;
void slove()
{
cin >> n >> m;
if( m == 1 )
{
if( n <= 1 ) cout << "1\n";
else cout << "-1\n";
return ;
}
res = ( n - m ) / ( m - 1 ) * 2 ;
if( (n-m)%(m-1) ) res += 3;
else res += 1;
cout << res << endl;
return ;
}
int main()
{
int t;
cin >> t;
while( t -- ) slove();
return 0;
}
H 牛牛看云
很搞笑，这道题我把这道题做复杂了
先说下真正的正解吧
说完了正解，在说一下我的方法，我的做法可以将\(a_i\)的范围加强到\(1e9\)甚至更大都可以
首先假设我对于我每次枚举的i之后，我把剩下的数字进行排序，然后我就可以用前缀和，二分把剩下序列分成\(a_i+a_j-1000<0\)和\(a_i+a_j\ge1000\)的部分，设mid为分界点那么
第二行就是前半部分，第三方就是后半部分，这里的\(a_k\)是已经排序后的
所以求解该式子需要先二分求出\(mid\)，然后前缀和即可，复杂度为\(O(\log n)\)
但是前提是每次都需要排序，在前缀和，所以求解真正复杂度应该是\(O(n\log n)\)，那么整体的复杂度就是\(O(n^2\log n)\)，这是基础的做法，然后讲优化
首先把a数组赋值给b并且排序，再用树状数组c维护b的前缀和，然后再用一个树状数组d维护一个全是1的数组的前缀和，d数组代表的就是b数组的每一位数字是否存在
每次对于一个a[i]在b数组中二分出\(a_j\ge 1000-a_i\)的最小值就是mid，然后用c,d两个数组就可以求解上面的式子，然后二分出a[i]在b中的位置，并且在c,d中的该位置分别加上-a[i],-1，这样在后面的过程中a[i]就被删除了
所以用两个树状数组的方法来优化复杂度就是\(O(n\log n)\)
#include <bits/stdc++.h>
#define ll long long
#define lowbit( x ) ( x & -x )
using namespace std;
const int N = 1e6 + 5;
int n , a[N] , b[N] ;
ll c[N] , d[N] , res;
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;
}
void update( int x , int v , ll bit[] )
{
for( int i = x ; i <= n ; i += lowbit(i) ) bit[i] += v;
}
ll get( int x , ll bit[] )
{
ll ans = 0;
for( int i = x ; i ; i -= lowbit(i) ) ans += bit[i];
return ans;
}
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 ; i <= n ; i ++ )
update( i , b[i] , c ) , update( i , 1 , d );
for( ll i = 1 , t , mid , k , sum , cnt; i <= n ; i ++ )
{
t = 1000 - a[i];
mid = lower_bound( b + 1 , b + 1 + n , t ) - b;
cnt = get( mid - 1 , d ) , sum = get( mid - 1 , c );
res += ( cnt * 2 + i - n - 1 ) * t + get( n , c ) - 2 * sum ;
k = lower_bound( b + 1 , b + 1 + n , a[i] ) - b;
update( k , -1 , d ) , update( k , -a[i] , c );
}
cout << res << endl;
}
J 小朋友做游戏
要保证a的数量一定是大于等于b的情况下，排个序贪心的选择就好了
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
long long n , sa , a , b , va[N] , vb[N] , res;
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;
}
void slove()
{
sa = a = read() , b = read() , n = read();
for( int i = 1 ; i <= a ; i ++ ) va[i] = read(); sort( va + 1 , va + 1 + a , greater<int>() );
for( int i = 1 ; i <= b ; i ++ ) vb[i] = read(); sort( vb + 1 , vb + 1 + b , greater<int>() );
b = min( b , n / 2 ) , a = min( a , n - b );
if( a + b < n )
{
cout << "-1\n";
return ;
}
res = 0 ;
while( a < sa && va[ a+1 ] > vb[b] ) a ++ , b --;
for( int i = 1 ; i <= a ; i ++ ) res += va[i];
for( int i = 1 ; i <= b ; i ++ ) res += vb[i];
cout << res << endl;
}
int main()
{
int t = read();
while( t -- ) slove();
return 0;
}
L 牛牛学走路
按照题目进行模拟不断地维护最大值即可
#include<bits/stdc++.h>
using namespace std;
int n ;
string op;
void slove()
{
cin >> n >> op;
double x = 0 , y = 0 , res = 0;
for( auto it : op )
{
if( it == 'L' ) x --;
else if( it == 'R' ) x ++;
else if( it == 'U' ) y ++;
else y --;
res = max( res , sqrt( x * x + y * y ) );
}
printf( "%.7lf\n" , res );
return ;
}
int main()
{
int t;
cin >> t;
while( t -- ) slove();
return 0;
}
AcWing 1904. 奶牛慢跑
这道题就是从后向前找一个不上升子序列，而且不能不选，开头也确定了
这道题的位置算是给无用的信息
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n , a[N] , t , cnt;
int main()
{
cin >> n;
for( int i = 1 , x ; i <= n ; i ++ )
cin >> x >> a[i];
t = a[n];
for( int i = n ; i >= 1 ; i -- )
{
if( a[i] > t ) continue;
t = a[i] , cnt ++;
}
cout << cnt << endl;
return 0;
}
Day3,4
AcWing 1922. 懒惰的牛
这道题的解法还是很多
最好理解的就是双指针，先按照位置排个序，然后同时维护l,r两个指针，保证指针的间距小于2k就行
#include <bits/stdc++.h>
#define w first
#define v second
using namespace std;
const int N = 1e5+5;
int n , k , sum , res , l , r;
pair< int , int > g[N];
int main()
{
cin >> n >> k;
for( int i = 1 ; i <= n ; i ++ )
cin >> g[i].v >> g[i].w;
sort( g + 1 , g + 1 + n ) , k *= 2;
for( int l = 1 , r = 1 ; r <= n ; r ++ )
{
sum += g[r].v;
while( g[r].w - g[l].w > k ) sum -= g[ l ++ ].v;
res = max( res , sum );
}
cout << res << endl;
return 0;
}
然后我发现这里\(x_i\)的范围很小*1e6，就完全可以用前缀和做，枚举每个区间就好了
#include <bits/stdc++.h>
#define w first
#define v second
using namespace std;
const int N = 1e6+5;
int n , k , res , v[N] , m ;
int main()
{
cin >> n >> k;
for( int i = 1 , x , y; i <= n ; i ++ )
scanf("%d%d" , &x , &y ) , m = max( m , y ), v[y] += x;
for( int i = 1 ; i <= m ; i ++ ) v[i] += v[ i - 1 ];
k = k * 2 + 1 ;
if( k >= m )
{
cout << v[m] << endl;
return 0;
}
for( int l = 0 , r = k ; r <= m ; r ++ , l ++ )
res = max( res , v[r] - v[l] );
cout << res << endl;
return 0;
}
如果说前缀和是站在牛的角度，还有就是可以差分站在草的角度做
如果草的位置是x那么在，草在x-k到x+k的贡献都是g，很简单前缀和维护就好了
#include <bits/stdc++.h>
#define w first
#define v second
using namespace std;
const int N = 3e6+10;
int n , k , res , v[N] , m ;
int main()
{
cin >> n >> k;
for( int i = 1 , l , r , x , y ; i <= n ; i ++ )
{
cin >> x >> y;
l = max( 1 , y - k ) , r = y + k , m = max( m , r );
v[l] += x , v[r+1] -= x;
}
for( int i = 1 ; i <= m ; i ++ )
v[i] += v[i-1] , res = max( res , v[i] );
cout << res << endl;
return 0;
}
前缀和的话要注意一下数组的范围应该是a+k也就是3e6不过也能过
AcWing 1884. COW
这道题就是很简单的思维题了
#include <bits/stdc++.h>
using namespace std;
string s;
long long a , b , c;
int main()
{
cin >> s >> s;
for( auto it : s )
{
if( it == 'C' ) a ++;
else if( it == 'O' ) b += a;
else c += b;
}
cout << c << endl;
return 0;
}
22牛客寒假训练营2
Day5,6
22牛客寒假训练营3
Acwing 周赛 36
A
非常简单的模拟
#include <bits/stdc++.h>
using namespace std;
string s;
set<char> t;
int main()
{
t.insert('a'),t.insert('e'),t.insert('i'),t.insert('o'),t.insert('u'),t.insert('y');
cin >> s;
for( auto & it : s )
if( it >= 'A' && it <= 'Z' ) it = it - 'A' + 'a';
for( int i = 0 ; i < s.size() ; i ++ )
{
if( t.find(s[i]) != t.end() ) continue;
cout <<'.'<< s[i];
}
return 0;
}
B
Day7
AtCoder Beginner Contest 237
2022寒假第一场摸底赛
A Haiku
其实就是统计一下字母的数量，用python很简单的
t = ["a","e","i","o","u"]
a = input()
b = input()
c = input()
x = 0
y = 0
z = 0
for i in t:
x += a.count(i)
y += b.count(i)
z += c.count(i)
if( x == 5 and y == 7 and z == 5 ):
print("YES")
else :
print("NO")
B Twisted Circuit
这道比第一道更加的签到
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n1 , n2 , n3 , n4;
int main()
{
cin >> n1 >> n2 >> n3 >> n4;
cout << ( ((n1^n2) & (n3 | n4)) ^ ((n2&n3) | (n1^n4)) ) << endl;
return 0;
}
C Hulk
就是一个循环就好
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
string s[2] = {"that I love ","that I hate "};
int main()
{
cin >> n;
cout << "I hate ";
swap( s[1] , s[0] );
for( int i = 1 ; i < n ; i ++ )
cout << s[i%2];
cout << "it";
return 0;
}
D Perfect Squares
把输入的数字排个序，从大到小依次先开方再平方不想等的就是答案
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1005;
int n , a[N] , ans;
int main()
{
cin >> n;
for( int i = 1 ; i <= n ; i ++ )
cin >> a[i];
sort( a + 1 , a + 1 + n , greater<int>());
for( int i = 1 , t ; i <= n ; i ++ )
{
t = sqrt( a[i] );
if( t * t != a[i] )
{
cout << a[i] << endl;
return 0;
}
}
return 0;
}
E Phone Code
两重循环喽
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 30005;
int n;
string s[N];
int main()
{
cin >> n;
for( int i = 1 ; i <= n ; i ++ )
cin >> s[i];
for( int i = 0 ; i < s[1].size() ; i ++ )
for( int j = 2 ; j <= n ; j ++ )
if( s[1][i] != s[j][i] )
{
cout << i << endl;
return 0;
}
cout << s[1].size() << endl;
return 0;
}
F Die Roll
数字太少，直接打表
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 30005;
int a , b;
string s[] = {"" , "1/1" , "5/6" , "2/3" , "1/2" , "1/3" , "1/6" };
int main()
{
cin >> a >> b;
a = max( a , b );
cout << s[a] << endl;
return 0;
}
G King Moves
情况只有三中间，边，顶点，所以特判一下就好
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 30005;
int a , b;
int y;
char x;
int main()
{
cin >> x >> y;
if( x >= 'b' && x <= 'g' && y >= 2 && y <= 7 ) cout << "8\n";
else if( ( x == 'a' || x == 'h' ) && ( y == 1 || y == 8 ) ) cout << "3\n";
else cout << "5\n";
return 0;
}
H 进制转换
跳过0就好了，特判第一个不输出加号
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll res , m , n;
string s;
int main()
{
cin >> m >> s;
n = s.size();
for( int i = 0 ; i < s.size() ; i ++ )
{
n --;
if( s[i] == '0' ) continue;
if( i != 0 ) cout << "+";
cout << s[i] << "*" << m <<"^"<< n;
}
return 0;
}
I 吃奶酪
90分很好做，就是dfs加点剪枝记忆化
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
double n,ans = 0x7f7f7f7f;
double x[N] = {},y[N] = {},f[N][N] = {};
bool vis[N] = {};
inline void dfs(int id,double now,int dep)
{
if(now > ans) return ;
if(dep == n)
{
ans = min(ans,now);
return ;
}
for(int i = 1 ;i <= n;i++)
{
if(!vis[i])
{
if(f[id][i])
{
vis[i] = 1;
dfs(i,now+f[i][id],dep+1);
vis[i] = 0;
}
else
{
f[id][i] = sqrt((x[id]-x[i])*(x[id]-x[i]) + (y[id]-y[i])*(y[id]-y[i]) );
f[i][id] = f[id][i];
vis[i] = 1;
dfs(i,now+f[id][i],dep+1);
vis[i] = 0;
}
}
}
}
int main()
{
cin >> n;
if(!n)
{
puts("0.00");
return 0;
}
for(register int i = 1;i <= n;i++) cin >> x[i] >> y[i];
dfs(0,0,0);
printf("%.2lf",ans);
return 0;
}
J Facer的工厂
如果剩余的加当前的大于等待长度就把剩余的先处理完，在放入
只要能完整的处理一秒就一直做
这道题我比赛是只拿到70分，因为没有开long long
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
ll n , m , k , last , res;
ll a[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() , k = read();
for( int i = 1 ; i <= n ; i ++ ) a[i] = read();
for( int i = 1 ; i <= n ; i ++ )
{
if( last + a[i] > m ) res ++ , last = 0;
last += a[i];
res += last / k , last %= k;
}
if( last ) res ++;
cout << res << endl;
}
K 炸铁路
这道题其实很暴力，就是先按照题目要求对边排序，然后依次判断边是否是key road即可
怎么判断呢？就是把除了这条边以外所有的边加入并查集，然后判断是否有一组点是不连通的就行
#include <bits/stdc++.h>
#define ll long long
#define u first
#define v second
using namespace std;
const int N = 155 , M = 5005l;
int n , m , fa[N];
pair< int , int > e[M];
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;
}
inline int getfa( int x )
{
if( fa[x] == x ) return x;
return fa[x] = getfa( fa[x] );
}
inline void merge( int x , int y )
{
x = getfa( x ) , y = getfa(y) ,fa[y] = x;
}
int main()
{
n = read() , m = read();
for( int i = 1 ; i <= m ; i ++ )
{
e[i].u = read() , e[i].v = read();
if(e[i].u>e[i].v) swap( e[i].u , e[i].v);
}
sort( e + 1 , e + 1 + m );
for( int t = 1 ; t <= m ; t ++ )
{
for( int i = 1 ; i <= n ; i ++ ) fa[i] = i;
for( int i = 1 ; i <= m ; i ++ )
{
if( i == t ) continue;
merge( e[i].u , e[i].v );
}
for( int i = 1 , fi , flag = 1 ; flag && i <= n ; i ++ )
{
fi = getfa(i);
for( int j = i + 1 ; flag && j <= n ; j ++ )
{
if( fi == getfa(j) ) continue;
cout << e[t].u << " " << e[t].v << endl;
flag = 0;
}
}
}
return 0;
}
L*阳光大学
其实可以把这个题理解成给一张图，要求每条边的两个点位于不同的集合中
这里我们可以用划分集合来表示，如果一条边的相同的集合中这一定不行
如果a于b相连，那么b一定于a相连的点在一个集合中
我代码中的color[x]，表示与x相连的点的集合
对于集合的为何这里需要用带权并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n,m,result,father[N],color[N],size[N];
bool f[N];
inline int read()
{
register int x = 0;
register char 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;
}
inline int getfather(int x)
{
if(father[x] == x) return x;
return father[x] = getfather(father[x]);
}
inline void merge(int x,int y)
{
if(x == y) return ;
father[y] = x;
size[x] += size[y];
}
int main()
{
n = read(); m = read();
for(register int i = 1; i <= n; i ++)
{
father[i] = i;
size[i] = 1;
}
for(register int i = 1;i <= m;i ++)
{
register int u = read(), v = read(), fu = getfather(u), fv = getfather(v);
if(fu == fv)
{
puts("Impossible");
return 0;
}
if(color[u]) merge(getfather(color[u]),fv);
if(color[v]) merge(getfather(color[v]),fu);
color[u] = fv; color[v] = fu;
}
for(register int i = 1;i <= n;i ++)
{
register int q = getfather(i);
if(f[q]) continue;
register int p = getfather(color[i]);
f[q] = f[p] = 1;
result += min(size[q],size[p]);
}
printf("%d\n",result);
return 0;
}
M 宝石管理系统
50分做法就暴力的排序喽
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n , m;
vector<ll> v;
inline ll read()
{
ll 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( ll x ; n ; n -- ) x = read() , v.push_back(x);
sort( v.begin() , v.end() , greater<ll>() );
for( ll op , x ; m ; m -- )
{
op = read() , x = read();
if( op == 1 ) printf("%lld\n" ,v[x-1] );
else v.push_back(x) , sort( v.begin() , v.end() , greater<ll>() );
}
return 0;
}
100分做法就是插入在小于等于它的位置就行
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n , m;
vector<ll> v;
inline ll read()
{
ll 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( ll x ; n ; n -- ) x = read() , v.push_back(x);
sort( v.begin() , v.end() , greater<ll>() );
for( ll op , x ; m ; m -- )
{
op = read() , x = read();
if( op == 1 ) printf("%lld\n" ,v[x-1] );
else v.insert( lower_bound( v.begin() , v.end() , x , greater<ll>() ) , x );
}
return 0;
}