3.4-3.10周报
周二天梯训练赛
天梯选拔赛一
A
这个题就是每次看到'.',就在它后面放一串英文字符"xixixixi."
L
其实就是看完整过了多少个视频，以及剩下的那个视频有没有播放到第m秒。
J
这个题wa了六发，好离谱，题读错了，其实就是每次都减去当前这个数字里任意一个数位，那我们就能有一个贪心思路，每次都减去最大的那个数，比如876，减去8一定比减去6更优。
点击查看代码
while(n>0){
int nn=n;
int max1=0;
while (nn > 0) {
int d = nn % 10;
nn /= 10;
max1=max(max1,d);
}
n-=max1;
ans++;
}
cout<<ans<<endl;
G
这个题也有坑，也不能算坑，就是我自己不认真读题，题目是选择三个方案中的其中一种，然后一直执行该操作，其实就是三个情况都跑一遍，看哪个最优就行。我第一遍读成了每一次操作都是三选一，也就是hard版的题意。其实就是个简单的贪心。
D
这个题还挺有意思的，我就是直接按照二维前缀和的做法套了个set，这样我就能得到每一个方框能得到的土豆情况，再把这些情况放进set里，是一个及其暴力的做法，但还好，过了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
//vector<pair<int,int>>d;
set<pair<int,int>>c[55][55];
set<set<pair<int,int>>>ss;
int a[55][55];
set<int>sx,sy;
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
int n;
cin>>n;
int minx=55,miny=55,maxx=-1,maxy=-1;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
a[x][y]=1;
//d.push_back({x,y});
sx.insert(x);
sy.insert(y);
minx=min(minx,x);
miny=min(miny,y);
maxx=max(maxx,x);
maxy=max(maxy,y);
}
//cout<<minx<<" "<<maxx<<" "<<miny<<" "<<maxy<<" "<<endl;
//sort(d.begin(),d.end());
for(int i=minx;i<=maxx;i++){
for(int j=miny;j<=maxy;j++){
if(a[i][j]==1)
c[i][j].insert({i,j});
if(j>=1)
c[i][j].insert(c[i][j-1].begin(),c[i][j-1].end());
if(i>=1)
c[i][j].insert(c[i-1][j].begin(),c[i-1][j].end());
//cout<<i<<" "<<j<<" "<<c[i][j].size()<<endl;
}
}
//cout<<"--\n";
//int x=d.size();
//cout<<x<<endl;
for(auto x1:sx){
for(auto x2:sx) {
for (auto y1:sy) {
for(auto y2:sy) {
set<pair<int, int>> e;
// int x1 = min(d[i].first, d[j].first);
// int x2 = max(d[i].first, d[j].first);
// int y1 = min(d[i].second, d[j].second);
// int y2 = max(d[i].second, d[j].second);
// cout << d[i].first << " " << d[i].second << " " << d[j].first << " " << d[j].second << endl;
//e.insert({d[i].first,d[i].second});
for (auto ee: c[x2][y2]) {
if (x1 >= 1 && y1 >= 1) {
if (c[x1 - 1][y2].count(ee) || c[x2][y1 - 1].count(ee)) {
continue;
} else {
e.insert(ee);
}
} else if (x1 >= 1) {
if (c[x1 - 1][y2].count(ee)) {
continue;
} else {
e.insert(ee);
}
} else if (y1 >= 1) {
if (c[x2][y1 - 1].count(ee)) {
continue;
} else {
e.insert(ee);
}
} else {
e.insert(ee);
}
}
// for (auto eee: e) {
// cout << eee.first << " " << eee.second << " ";
// }
// cout << endl;
ss.insert(e);
}
}
}
}
cout<<ss.size()<<endl;
return 0;
}
B
这道题其实就是简单的差分前缀和问题，想要每个鸡蛋都达到所需要的温度，不就是初始温度为负的所需要的温度，执行完当前方案后看看是不是所有的鸡蛋都变成了0度以上，只要是就是合理的，然后找到最便宜的方案即可。
点击查看代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int a[110],b[110],c[110];
struct node{
int l,r,k,p;
}d[15];
void solve(long long kk) {
int n,m;
int sum=LLONG_MAX;
int N=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
int l,r,m;
cin>>l>>r>>m;
a[l]+=(-m);
a[r+1]-=(-m);
N=max(N,r);
}
// for(int j=1;j<=N;j++){
// b[j]=b[j-1]+a[j];
// //cout<<j<<" "<<b[j]<<" ";
// }
// cout<<endl;
for(int i=1;i<=m;i++){
cin>>d[i].l>>d[i].r>>d[i].k>>d[i].p;
}
//cout<<"----\n";
for(int i=0;i<=(1<<m)-1;i++){
memset(b,sizeof(b),0);
for(int j=1;j<=N;j++){
c[j]=a[j];
}
int x=i;
int f=0;
int asum=0;
for(int j=1;j<=m;j++){
if(x%2==1){
c[d[j].r+1]-=d[j].k;
c[d[j].l]+=d[j].k;
asum+=d[j].p;
}
//cout<<x%2;
x/=2;
}
//cout<<endl;
for(int j=1;j<=N;j++){
b[j]=b[j-1]+c[j];
//cout<<b[j]<<" ";
if(b[j]<0){
f=1;
}
}
//cout<<endl;
if(f==0)
sum=min(sum,asum);
//cout<<f<<" "<<asum<<endl;
}
cout<<sum<<endl;
return ;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
long long T = 1;
//cin >> T ;
for(long long i=1;i<=T;i++) solve(i);
return 0;
}
赛时只过了这几道题，赛后又补了几道题。
I
这个题其实之前做过类似的题，只是我赛时没想起来，要找到这个数有多少个因数，其实就是找质因数，然后求一下组合数，比如54可以分为3个3和1个2，因数就是4*2=8个，选不选这个质因数以及选几个质因数的问题。其实代码的重点就是预处理一下有多少个质因数以及求组合数。
点击查看代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
set<int>s;
int prime[50000];
int f[100010];
void shaishu(int n){
int ans=1;
for(int i=2;i<=n;i++){
if(f[i]==1)
continue;
else{
prime[ans++]=i;
}
for(int j=2;i*j<=n;j++){
f[i*j]=1;
}
}
}
void solve(long long kk) {
int n;
cin>>n;
int sum=1;
for(int i=1;prime[i]<=sqrt(n);i++){
if(n%prime[i]==0){
int ans=0;
while(n){
if(n%prime[i]==0){
ans++;
}
else{
break;
}
n/=prime[i];
}
sum*=(ans+1);
}
}
if(n!=1){
sum*=2;
}
cout<<sum<<endl;
return ;
}
signed main() {
// ios::sync_with_stdio(0);
// cin.tie(0) , cout.tie(0);
long long T = 1;
shaishu(100000);
cin >> T ;
for(long long i=1;i<=T;i++) solve(i);
return 0;
}
H
这个题就是G题的hard版，也就是我一开始读错题的版本，其实就是个dp,只是dp思路有点难想明白。
dp[l][r]l就是左端点，r就是右端点，当长度等于2时，其实可以理解为赋初值，它的值就是两个位置的数字和模3，当长度大于2时就可以由递推式得出，当前这个长度的值是从左边拿两个，从右边拿两个以及左右各一个三种情况得来的，找最大值即可。
最后dp[1][n]就是最后的结果。
点击查看代码
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
int l = j,r = j + i - 1;
if (r > n) continue;
if (l >= r) continue;
if (r - l + 1 == 2) dp[l][r] = (a[l] + a[r]) % 3;
else{
dp[l][r] = max({dp[l][r],(a[l] + a[l + 1]) % 3 + dp[l + 2][r],(a[r] + a[l]) % 3 + dp[l + 1][r - 1],(a[r] + a[r - 1]) % 3 + dp[l][r - 2]});
}
}
}
cout<< dp[1][n] <<endl;
牛客寒假集训营1
A
这个题就是看DFS和dfs是不是当前字符串的子序列。其实很简单了就是遍历一遍就行。
M
每次只能显示6个题，向左和向右移动都只能移动六个题，除非没有题了，就顶到最后一个题，其实我们用7个题就能找到规律，就是有没有余数的问题，有余数就是几个6的二倍，否则就是几个6
G
这个题就是，满a减b，但是优惠券可以叠加，那就是贪心了，看最大可用的优惠券面值是多大，比它更小的就都可以用了。
C
这道题需要知道一个前提就是，这个队伍的排列就是按照办事时间排序，越小的人越先办，那其实就是看工作人员的忍耐度允许这个人插几个人的队，只有这几个被插队的人的不满意度才会增加，那也就是前几个人办完的时间加上这个人的办事时间。
L
这个题其实有很多干扰条件，只需要看光照大地的面积，那就只需要画出来xoy平面的图就可以，灯放在x轴是最优的方案，直接带入求面积就可以了。
B
这道题其实主要就是想明白一个点，最多也就是填三个点（2，0），（1，-1）（1，1），这三个点就能让无法逃脱，还有一点就是不只有直线，相邻的斜对角也会把它堵住。
点击查看代码
#include "bits/stdc++.h"
using namespace std;
#define int long long
set<pair<int, int>> s;
void solve() {
s.clear();
int n;
cin >> n;
int ans0 = 2, ans1 = 2;
for (int i = 0; i < n; i++) {
int r, c;
cin >> r >> c;
s.insert({r, c});
if (c <= 0) {
ans0 = 1;
}
if (c >= 0) {
ans1 = 1;
}
}
for (auto e : s) {
int r=e.first;
int c=e.second;
for (int i = -1; i < 2; i++) {
if (s.count({r ^ 3, c + i})) {
if (c < 0) {
ans0 = 0;
}
if (c > 0) {
ans1 = 0;
}
}
}
}
int ans = 3 - s.count({2, 0}) - s.count({1, -1}) - s.count({1, 1});
cout << min(ans, ans0 + ans1) << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}