2022寒假训练week2
Day 1 - Day5
AcWing 2014. 岛
首先要对每个点进行离散化，然后对于相邻的相同高度的点进行去重，然后按照高度排序，并枚举每一个点
对于每个点有三种情况
- 两侧都比中间高，淹没该点后小岛数+1
- 两侧都比中间低，淹没该点后小岛数-1
- 两侧一高一低，淹没该点后小岛数不变
虽然去重后相邻的点不会一般高，但是会出现不相邻的点被同时淹没的情况
#include
using namespace std;
const int N = 1e5+5;
int h[N] , n;
pair q[N];
int main()
{
cin >> n;
for( int i = 1 ; i <= n ; i ++ ) cin >> h[i];
n = unique( h + 1 , h + 1 + n ) - h - 1 , h[n+1] = 0;
for( int i = 1 ; i <= n ; i ++ ) q[i]= { h[i] , i } ;
sort( q + 1 , q + 1 + n );
int res = 1 , cnt = 1;
for (int i = 1 , k , nh ; i <= n; i ++ )
{
nh = q[i].first , k = q[i].second;
if( h[k-1] > nh && h[k+1] > nh ) cnt ++;
else if( h[k-1] < nh && h[k+1] < nh ) cnt --;
if( nh != q[i+1].first ) res = max( res , cnt );
}
cout << res << endl;
}
AcWing 2005. 马蹄铁
这道题因为数据范围比较小可以进行不加优化的暴搜即可，但是要判断)(这样的不合法情况
#include
using namespace std;
const int N = 7 , dx[] = { 0 , 0 , 1 , -1 } , dy[] = { 1 , -1 , 0 , 0 };
int n , ans;
bool vis[N][N];
string st[N];
void dfs( int x , int y , int l , int r )
{
vis[x][y] = 1;
if( l == r )
{
ans = max ( l * 2 , ans );
vis[x][y] = 0;
return ;
}
for( int i = 0 , a , b ; i < 4 ; i ++ )
{
a = x + dx[i] , b = y + dy[i];
if( a < 0 || a >= n || b < 0 || b >= n || vis[a][b] ) continue;
if( r > 0 && st[a][b] == '(' ) continue;
if( st[a][b] == '(' ) dfs( a , b , l + 1 , r );
else dfs( a , b , l , r + 1 );
}
vis[x][y] = 0;
}
int main()
{
cin >> n;
for( int i = 0 ; i < n ; i ++ ) cin >> st[i];
if( st[0][0] == '(' ) dfs( 0 , 0 , 1 , 0 );
cout << ans << endl;
return 0;
}
AcWing 1996. 打乱字母
贪心+二分
首先我们可以把每个字符串排序（升序），然后把字符串按照字典序排序，在二分出大于等于每个字符串降序排序的位置就是最小的位置
反过来就能得到最大的位置
#include
using namespace std;
const int N = 5e4+5;
int n;
string a[N] , b[N] , c[N];
int main()
{
cin >> n;
for( int i = 1 ; i <= n ; i ++ )
{
cin >> a[i];
b[i] = c[i] = a[i];
sort( b[i].begin() , b[i].end() , greater() );
sort( c[i].begin() , c[i].end() );
}
sort( b + 1 , b + 1 + n ) , sort( c + 1 , c + 1 + n);
for( int i = 1 , k ; i <= n ; i ++ )
{
sort(a[i].begin() , a[i].end() );
k = lower_bound( b + 1 , b + 1 + n , a[i] ) - b;
cout << k << ' ' ;
reverse( a[i].begin() , a[i].end() );
k = upper_bound( c + 1 , c + 1 + n , a[i] ) - c - 1;
cout << k << '\n';
}
}
AcWing 1952. 金发姑娘和 N 头牛
如果吧数轴上每一个点当做是，这个点温度对于最大收益，本质上就是每次给三个区间做区间修改
区间修改可以用差分来实现，然后随机范围比较大需要用离散化
#include
using namespace std;
const int inf = 2e9;
map< int , int > b;
int main()
{
int n , x , y , z;
cin >> n >> x >> y >> z;
for( int i = 1 , l , r ; i <= n ; i ++ )
{
cin >> l >> r;
b[ -inf ] += x , b[ l ] += y - x , b[ r + 1 ] += z - y , b[ inf ] -= z;
}
int res = 0 , sum = 0;
for( auto & [ k , v ] : b )
sum += v , res = max( res , sum );
cout << res << endl;
return 0;
}
AcWing 1945. 奶牛棒球
这里因为数据范围只有1000，题目要求是 y - x <= z - y <= 2 * ( y - z ) && x <= y <= z
所以可以枚举x,y然后二分出z的范围即可
#include
using namespace std;
int n , a[1005] , res;
int main()
{
cin >>n;
for( int i = 1 ; i <= n ; i ++ ) cin >> a[i];
sort( a + 1 , a + 1 + n );
for( int i = 1 , l , r , t ; i <= n ; i ++ )
{
for( int j = i + 1 ; j <= n ; j ++ )
{
t = a[j] - a[i];
l = lower_bound( a + 1 + j , a + 1 + n , a[j] + t ) - a;
r = upper_bound( a + 1 + j , a + 1 + n , a[j] + 2 * t ) - a;
res += r - l;
}
}
cout << res << endl;
}
Day 6
Acwing 第35场周赛
A 4212. 字符串比较
签到题，可以直接用Python水过
a = input().lower()
b = input().lower()
if a == b :
print("0")
elif a > b :
print("1")
else :
print("-1")
这里补充两个常用函数
str = "AbcdE"
str.lower()
# 将字符串中所有大写转换成小写
str.upper()
# 将字符串中所有小写转化成大写
B 4213. 最小结果
因为数据范围很小，可以直接用爆搜枚举所有的情况
用一个vector来存储剩下的数字
#include
#define ll long long
using namespace std;
ll res = 1LL << 60 ;
char op[5];
void dfs( vector v , int u )
{
if( u == 3 )
{
res = min ( res , v[0] );
return ;
}
for( int i = 0 ; i < v.size() ; i ++ )
{
for( int j = i + 1 ; j < v.size() ; j ++ )
{
vector t;
for( int k = 0 ; k < v.size() ; k ++ )
if( k != i && k != j ) t.push_back(v[k]);
if( op[u] == '+' ) t.push_back( v[i] + v[j] );
else t.push_back( v[i] * v[j] );
dfs( t , u + 1 );
}
}
}
int main()
{
vector t(4);
for( int i = 0 ; i < 4 ; i ++ ) cin >> t[i];
for( int i = 0 ; i < 3 ; i ++ ) cin >> op[i];
dfs( t , 0 );
cout << res << endl;
}
Codeforce Round #767(Div.2)
A
一开始有一个内存k，有n个程序，每次运行一个程序会消耗内存a，程序运行结束会回收内存a并获得额外的内存b，问最多可以达到多少内存？
按照a排序，贪心的运行就好了
#include
using namespace std;
const int N = 105;
int n , k;
pair< int , int > soft[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;
}
void slove()
{
n = read() , k = read();
for( int i = 1 ; i <= n ; i ++ ) soft[i].first = read();
for( int i = 1 ; i <= n ; i ++ ) soft[i].second = read();
sort( soft + 1 , soft + 1 + n );
for( int i = 1 ; i <= n ; i ++ )
{
if( k < soft[i].first ) break;
k += soft[i].second;
}
printf("%d\n" , k );
return;
}
int main()
{
int t = read();
while ( t-- ) slove();
return 0;
}
B
这道题的解题思路十分的诡异，我目前还没有看正解，也不知到该如何证明
首先题目的意思是每次进行一个操作，操作就是随机选择两个数删除，并插入两个数的乘积，问k次操作后能否让数列的gcd大于1
首先我知道如果gcd大于1则至少是2，而奇数与奇数，奇数与偶数之间的gcd一定不是2，也就是说只要让一个数列全部是偶数，那么他的gcd就是至少是2，然后我们知道奇数与偶数相乘是偶数，如果一个数列长度大于1，就必定有奇数也有偶数，所以只要数列种奇数的个数小于等于操作数k，就一定可以吧数列变成偶数，则gcd就一定打于1
#include
using namespace std;
const int N = 105;
int l , r , k , t ;
pair< int , int > soft[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;
}
void slove()
{
l = read() , r = read() , k = read();
if( l == r && l != 1 )
{
printf("YES\n");
return;
}
t = ( ( l & 1 ) && ( r & 1 ) ) + ( ( r - l + 1) >> 1 );
if( t <= k ) printf("YES\n");
else printf("NO\n");
return;
}
int main()
{
int t = read();
while ( t-- ) slove();
return 0;
}
Day 7
AtCoder Beginer Contest 236
A
签到题目，直接swap
#include
using namespace std;
string s;
int a , b;
int main()
{
cin >> s >> a >> b;
swap( s[a-1] , s[b-1] );
cout << s << endl;
return 0;
}
B
考翻译的，有一副牌，每个数字有四张，现在抽走一样，给剩下的牌，问抽走了那一张？
签到
#include
using namespace std;
const int N = 1e5+5;
int n , a[N];
int main()
{
cin >> n;
for( int i = 1 , x ; i < 4 * n ; i ++ )
{
cin >> x ;
a[x] ++;
}
for( int i = 1 ; i <= n ; i ++ )
{
if( a[i] != 4 )
{
cout << i << endl;
return 0;
}
}
return 0;
}
C
还是考翻译的，给一些点，在告诉你经过了那些点，问每一个点时候经过
这里的就是给的不是编号而是站点的名字，所以做一个简单的hash就行了
#include
using namespace std;
const int N = 1e5+5;
int n , m;
string key[N];
unordered_map< string , bool >q;
int main()
{
cin >> n >> m;
string cur;
for( int i = 1 ; i <= n ; i ++ )
{
cin >> key[i];
q[key[i]] = 0;
}
for( int i = 1 ; i <= m ; i ++ )
{
cin >> cur;
q[cur] = 1;
}
for( int i = 1 ;i <= n ; i ++ )
{
if( q[ key[i] ] ) printf("Yes\n");
else printf("No\n");
}
return 0;
}
D
有2n个人，每两个人结合成一组的都有一个权值，让所有的人分组后，权值的异或和最大即可
这里最多是16个人，如果直接爆搜会tle，要考虑优化
用一个bool数组判断每个人时候已经结合，如果每次用数组存剩下的人会tle
然后就是根据异或满足交换律，所以的顺序不影响结果，那么我们在枚举时，第一个人不需要枚举，就找第一个没有很分组的，然后枚举第二个即可
这样的最多只有2027025种情况，完全可以接受
#include
#define ll long long
using namespace std;
const int N = 20;
int n;
ll a[N][N] , res;
bool vis[N];
void dfs( int cnt, ll ans )
{
if( cnt == 0 )
{
res = max( res , ans );
return ;
}
for( int i = 1 ; i <= n ; i ++ )
{
if( vis[i] ) continue;
vis[i] = 1;
for( int j = i + 1 ; j <= n ; j ++ )
{
if( vis[j] ) continue;
vis[j] = 1;
dfs( cnt - 2 , ans ^ a[i][j] );
vis[j] = 0;
}
vis[i] = 0;
break;
}
return;
}
int main()
{
cin >> n;
n *= 2;
for( int i = 1 ; i < n ; i ++ )
for( int j = i + 1 ; j <= n ; j ++ ) cin >> a[i][j];
dfs( n , 0 );
cout << res << endl;
return 0;
}