【LittleXi】AK题解
A
题解：
签到题，白色便宜就打白色，彩色便宜就打彩色
代码：
#include<iostream>
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;
#define endl "\n"
#define ll long long
void solve(){
ll a,b,x,y;
if(x > y) b += a,a= 0;
cout<<a*x + b*y<<endl;
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
ll t;cin>>t;
while(t--)
solve();
}
B
题解：
贪心，每次让n变为能到达的最大的数字
如果是奇数就n/2 , 偶数就是 n/2-1
代码：
#include<iostream>
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;
#define endl "\n"
#define ll long long
void solve(){
ll n;cin>>n;
int ans = 0;
while(n){
if(n&1) n = n/2;
else n = n/2 - 1;
ans ++;
}
cout<<ans<<endl;
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
ll t;cin>>t;
while(t--)
solve();
}
C
题解：
将S能到达的地区标记为1，E能到达的地区标记为2，然后判定每个2的附近3行行列是否有1，有的话就可以直接贯穿
代码：
#include<iostream>
#include<bits/stdc++.h>
#include<set>
#include<map>
#include<queue>
using namespace std;
#define endl "\n"
#define ll long long
void solve() {
int n, m; cin >> n >> m;
vector<string> grid(n);
for (auto& x : grid) cin >> x;
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 'S') {
q.push({ i,j });
}
}
}
auto msk1 = grid;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
while (q.size()) {
auto p = q.front(); q.pop();
int x = p.first, y = p.second;
msk1[x][y] = '1';
for (int i = 0; i < 4; i++) {
int tox = x + dx[i], toy = y + dy[i];
if (tox < 0 || tox >= n || toy < 0 || toy >= m) continue;
if (grid[tox][toy] == '#') continue;
if (msk1[tox][toy] == '1') continue;
msk1[tox][toy] = '1';
q.push({ tox,toy });
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 'E') {
q.push({ i,j });
}
}
}
auto msk2 = grid;
while (q.size()) {
auto p = q.front(); q.pop();
int x = p.first, y = p.second;
msk2[x][y] = '2';
for (int i = 0; i < 4; i++) {
int tox = x + dx[i], toy = y + dy[i];
if (tox < 0 || tox >= n || toy < 0 || toy >= m) continue;
if (grid[tox][toy] == '#') continue;
if (msk2[tox][toy] == '2') continue;
msk2[tox][toy] = '2';
q.push({ tox,toy });
}
}
vector<int> h1(n, 0), z1(m, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (msk1[i][j] == '1') {
h1[i] = 1; z1[j] = 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (msk2[i][j] == '2') {
for(int k = -1;k<=1;k++){
if(i + k >= 0 && i + k < n && h1[i+k]){
cout << "YES" << endl; return;
}
if(j + k >= 0 && j + k < n && z1[j+k]){
cout << "YES" << endl; return;
}
}
}
}
}
cout << "NO" << endl;
}
signed main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
solve();
}
D
题解：
根据素数的稠密性，直接开一个长度为100n的数字，进行暴力剔除不满足的时间
代码:
#include<iostream>
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;
#define endl "\n"
#define ll long long
void solve(){
int n;cin>>n;
vector<int> a(n);
for(int&x:a) cin>>x;
int m = 2*n + 10;
vector<int> dp(m,0);
set<int> se(a.begin(),a.end());
for(int x:se){
for(int j = x; j<m;j+=x){
dp[j] = 1;
}
}
for(int i = 2;i<m;i++){
if(dp[i] == 0){
cout<<i<<endl;return;
}
}
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
ll t;cin>>t;
while(t--)
solve();
}
E
题解：
将能连续倒塌的多米诺骨牌看作一个块，将每个块取出来，贪心取m个就行
代码：
#include<iostream>
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;
#define endl "\n"
#define ll long long
void solve(){
ll n,m;cin>>n>>m;
vector<pair<ll,ll>> vp(n);
for(ll i =0;i<n;i++) cin>>vp[i].first;
for(ll i =0;i<n;i++) cin>>vp[i].second;
for(ll i =0;i<n;i++) swap(vp[i].first , vp[i].second);
sort(vp.begin(),vp.end());
vector<ll> k;
ll p = 0;
while(p < n){
ll rp = vp[p].first + vp[p].second;
ll sz = 1;
while(p + 1 < n && rp >= vp[p+1].first){
p ++;sz ++;
rp = max(rp , vp[p].first + vp[p].second);
}
p++;
k.push_back(sz);
}
sort(k.begin(),k.end());
reverse(k.begin(),k.end());
ll ans = 0;
for(ll i =0 ;i<k.size() && i < m;i++){
ans += k[i];
}
cout<<ans<<endl;
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
ll t;cin>>t;
while(t--)
solve();
}
F
题解：
对于每两个相邻的墙，我们能获取2*dis的时间，那么一共有2 * m的不同时间，直接进行完全背包即可
代码：
#include<iostream>
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;
#define endl "\n"
void solve(){
int n,m,t;cin>>n>>m>>t;
vector<int> a(m);
for(int&x:a) cin>>x;
if(n>t){
cout<<0<<endl;return;
}
sort(a.begin(),a.end());
set<int> b;
for(int i=1;i<m;i++) b.insert(a[i] - a[i-1]);
vector<int> w;
for(int x:b) w.push_back(x);
vector<int> dp(t+1,0);
dp[n] = 1;
for(int x:w){
for(int j =0;j<=t;j++){
if(j + 2*x > t) continue;
if(dp[j]){
dp[j + 2*x ] |= dp[j];
}
}
}
for(int i = t;i>=0;i--){
if(dp[i]){
cout<<i<<endl;return;
}
}
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
int t;cin>>t;
while(t--)
solve();
}
G
题解：
暴力维护每个时间点的各种🐟的状态，然后从x暴力跳最大能吃的，因为每次x加倍，所有跳lgw次，这个用set+离散化+树状数组维护区间sum就行
代码
#include<iostream>
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;
//坐标从0开始直接用的树状数组
#define ll long long
template <typename T>
class Fenwick
{
private:
ll n;
vector<T> c;
ll lowbits(ll x){
return (-x) & x;
}
ll pre_sum(ll i){
ll re = 0;
for (; i > 0; i -= lowbits(i))
re += c[i];
return re;
}
public:
explicit Fenwick<T>(vector<T> v){
this->n = v.size();
this->c = vector<T>(n+1,0);
for(ll i=0;i<n;i++)
add(i,v[i]);
};
void add(ll i, ll val){
++i;
for (;i<=n; i += lowbits(i))
c[i] += val;
}
ll range_sum(ll i,ll j){
++i;++j;
return pre_sum(j) - pre_sum(i - 1);
}
};
void solve(){
ll n,x;cin>>n>>x;
vector<vector<ll>> vp;
vector<ll> b;
for(ll i =0 ;i<n;i++){
ll l,r,y;cin>>l>>r>>y;
vp.push_back({l,y,0});
vp.push_back({r,y,1});
b.push_back(y);
}
sort(b.begin(),b.end());
map<ll,ll> mp;
// 离散化
for(ll i =0 ;i<n;i++) mp[b[i]] = i;
Fenwick<ll> fw(vector<ll>(n,0));
sort(vp.begin(),vp.end());
multiset<ll> se;
ll ans = 0;
for(ll i = 0;i<2*n;){
ll p1 = vp[i][0] , y = vp[i][1] , op = vp[i][2];
while(i<2*n && vp[i][0] == p1){
ll ny = vp[i][1] , nop = vp[i][2];
if(nop==0){
se.insert(ny);
fw.add(mp[ny],ny);
}else{
se.erase(se.find(ny));
fw.add(mp[ny],-ny);
}
i++;
}
// 找答案
ll tval = x;
ll pos = 0;
while(1){
auto it = se.lower_bound(tval);
if(it==se.end()){
tval += fw.range_sum(pos,n-1);break;
}
if(*it > tval){
if(it==se.begin()) break;
it = prev(it);
}
ll pr = mp[*it];
if(pr < pos) break;
tval += fw.range_sum(pos , pr);
pos = pr + 1;
}
ans = max(ans, tval);
}
cout<<ans<<endl;
}
signed main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(0);
ll t;cin>>t;
while(t--)
solve();
}
*****************************
