AtCoder Beginner Contest 406(ABCD)

前言

我仿佛在梦游……

一、A - Not Acceptable

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int dueH,dueM,upH,upM;cin>>dueH>>dueM>>upH>>upM;if(upH>dueH){cout<<"No";}else if(upH<dueH){cout<<"Yes";}else{if(upM>dueM){cout<<"No";}else{cout<<"Yes";}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

签到题，没啥好说的。

二、B - Product Calculator

#include <bits/stdc++.h>
using namespace std;typedef unsigned long long ll;//我阐述你的梦的伞兵unsigned long long
typedef pair<int,int> pii;void solve()
{int n,k;cin>>n>>k;vector<ll>nums(n+1);for(int i=1;i<=n;i++){cin>>nums[i];}vector<int>bits(k);bits[0]=1;for(int i=1;i<=n;i++){ll num=nums[i];ll t=0;for(int j=0;j<k;j++){t+=bits[j]*num;bits[j]=t%10;t/=10;}if(t>0){bits[0]=1;for(int i=1;i<k;i++){bits[i]=0;}}}bool skip=true;for(int i=k-1;i>=0;i--){if(skip&&bits[i]!=0){skip=false;}if(!skip){cout<<bits[i];}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

这个b题真的搞心态，开到long long会一直过不去，一道题卡了我四十多分钟，一直找不到问题出在哪，最后换了unsigned long long才能过……

思路类似高精度算法，因为最多k位，所以就开个长度为k的数组，每个位置表示结果里第i位的数。所以就是设置一个t表示进位信息，然后对于每个数乘以当前位的结果加上进位信息再模10就是乘后当前位的数字，之后进位信息需要除以10往下一位传递。若k位都遍历结束后还存在进位信息t，说明此时乘积超出了范围，那就把bits数组还原即可。

最后，在输出时要记得避免输出高位的0。

三、C - ~

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//有五个用例一直过不去……
ll way1(int n,vector<int>&nums)
{ll ans=0;int a=0,b=0,c=0,d=0;while(a+1<n&&nums[a]>nums[a+1]){a++;}if(a>=n-3){return 0;}c=a;//注意要对齐！！！防止“1 1 2 1 1 2”最后c!=a会多计算for(int i=a;i<n-1;i++){if(nums[i-1]<nums[i]&&nums[i]>nums[i+1])//极大值{if(b==0){b=i;}else{d=i;}}if(nums[i-1]>nums[i]&&nums[i]<nums[i+1])//极小值{c=i;}if(b!=0&&d!=0){ans+=(ll)(b-a)*(d-c);//我阐述你的梦的long longb=d;d=0;a=c;}}if(c!=a)//有极小值但无第二个极大值{d=n-1;ans+=(ll)(b-a)*(d-c);//我阐述你的梦的long long}return ans;
}void solve()
{int n;cin>>n;vector<int>nums(n);for(int i=0;i<n;i++){cin>>nums[i];}cout<<way1(n,nums);}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

我真草了这个long long……之前牛客上的一个题也是，怎么都过不去，对数器跑十几万次都没问题，最后发现还是中间做乘法的时候没开long long……真的恶心啊啊啊啊啊！！！！！赛时都写出来了，然后又是被long long卡到结束都没发现……

思路很简单，首先就是观察这四个条件，可以发现就是要求找极大值和极小值，然后再结合开头的条件，可以发现必须是极大值、极小值、极大值的顺序，然后只要存在一个极大值和极小值，也就自然保证至少四个点。再观察可以发现，对于每个极大值和极小值的区间，因为要求是连续的子数组，所以只能是开头上升的一段上的点的个数乘以极小值后上升的那一段的点的个数。

所以就是遍历一遍找极大值和极小值，然后计算开头和结尾两区间的个数即可。注意边界情况的讨论！！

四、D - Garbage Removal

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int h,w,n;cin>>h>>w>>n;//害，原本以为这种每一个操作都遍历的方法肯定会TLE的vector<set<int>>rows(h+1);vector<set<int>>cols(w+1);for(int i=0,x,y;i<n;i++){cin>>x>>y;rows[x].insert(y);cols[y].insert(x);}int q;cin>>q;for(int i=1,op,num;i<=q;i++){cin>>op>>num;if(op==1)//行{cout<<rows[num].size()<<endl;for(auto iter:rows[num]){cols[iter].erase(num);}rows[num].clear();}else//列{cout<<cols[num].size()<<endl;for(auto iter:cols[num]){rows[iter].erase(num);}cols[num].clear();}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();    }return 0;
}

这个题真的，我一开始还想着是不是得设计个结构可以在小于O(n)的时间内快速删除，结果还真是遍历一遍全删除……

就是用一个set存有垃圾的位置，然后对于行清除和列清除就去set里全删了。

总结

E题真不行了……

END