240309 美团春招笔试代码-ak
很久不做题了，可能上次笔试还是去年10月的事情了。题目总的来说还是挺正常的，就是题面写的不太好，最后一题很多边界情况没解释清楚，需要自己推理尝试。写了一个小时ak了就交了，实习，秋招，春招三次笔试好像都是一个小时做完的。
int main(){
int _t = 1;
// cin>>_t;
while(_t--) {
int n,k;cin>>n>>k;
string s;cin>>s;
int left = 0;
for(auto &c:s){
left += c!='M' && c!='T';
}
left -= min(left,k);
cout<<s.size() - left<<endl;
}
return 0;
}
int main(){
int _t = 1;
// cin>>_t;
while(_t--) {
int n,q;cin>>n>>q;
int cnt = 0;
for(int i = 1;i<=n;i++)scanf("%d",&a[i]),cnt+=a[i] == 0;
ll summ = accumulate(a+1,a+1+n,0LL);
while(q--){
ll l,r;scanf("%lld %lld",&l,&r);
cout<<summ + l * cnt <<" "<<summ + r *cnt<<endl;
}
}
return 0;
}
知识点考的是二维前缀和，真的是好久没写过。因为求的是一个正方形的01数量，所以复杂度是nnn的。
int main(){
int _t = 1;
// cin>>_t;
while(_t--) {
memset(arr,0,sizeof arr);
int n;cin>>n;
int res = 0;
map<int,int> m;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
char c;cin>>c;
arr[i][j] = c-'0';
arr[i][j] += arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1];
for(int len = 1;len<=min(i,j);len++){
int cnt = arr[i][j] - arr[i][j - len] - arr[i-len][j]+arr[i-len][j-len];
if(cnt * 2 == len * len)m[len]++;
}
}
}
for(int i = 1;i<=n;i++){
cout<<m[i]<<endl;
}
}
return 0;
}
老结论了，0的数量由2/5的数量共同决定。所以删除一个区间后，剩下的0的数量可以由2，5数量的最小值确定。我们先求整体的2，5数量。然后用双指针去更新，对于每一个i，找到其左边的合理的最左边的j，使得删除从j到i之间都能使得0的数量足够。
int main(){
int _t = 1;
// cin>>_t;
while(_t--) {
int n,k;cin>>n>>k;
for(int i = 1;i<=n;i++)scanf("%d",&a[i]);
vector<pii> v;
v.push_back({0,0});
int c2tt = 0,c5tt = 0;
for(int i = 1;i<=n;i++){
int ac = 0,bc = 0;
int u = a[i];
while((u%2)==0){
ac++;
u/=2;
}
while((u%5)==0){
bc++;
u/=5;
}
v.push_back({ac,bc});
c2tt += ac,c5tt += bc;
}
int c2 = 0,c5 = 0;
int j = 1;
ll res = 0;
for(int i = 1;i<=n;i++){
c2 += v[i].first,c5+=v[i].second;
while(j<=i && min(c2tt-c2,c5tt-c5)<k){
c2-=v[j].first,c5-=v[j].second;
j++;
}
res += max(i-j+1,0);
}
cout<<res<<endl;
}
return 0;
}
正难则反，因为传统并查集不支持删除操作（是有这么个数据结构，但是我不会），倒序把删除操作变成添加边的操作。然后正常查询是否连接，最后将结果倒序输出。（其实思路还是挺简单的，就是一个是序号是1-1e9，需要先做离散化。其次是会出现一些不在离散化列表里的数据，和一些无意义的非法操作，需要针对性的特判，这里卡了我挺长时间）
#include<iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <list>
#include <functional>
#include <algorithm>
#include <memory>
#include <numeric>
#include <unordered_set>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int a[200010];
int p[200010];
int find(int x){
if(p[x]!=x){
p[x] = find(p[x]);
}
return p[x];
}
int main(){
int _t = 1;
// cin>>_t;
while(_t--) {
int n,m,q;cin>>n>>m>>q;
unordered_map<int,unordered_set<int>> gra;
unordered_map<int,unordered_set<int>> old_gra;
int id = 1;
iota(p+1,p+1+200000,1);
unordered_map<int,int> map_person;
for(int i = 1;i<=m;i++){
int u,v;scanf("%d %d",&u,&v);
if(!map_person.count(u))map_person[u] = id++;
if(!map_person.count(v))map_person[v] = id++;
gra[map_person[u]].insert(map_person[v]);
gra[map_person[v]].insert(map_person[u]);
old_gra[map_person[u]].insert(map_person[v]);
old_gra[map_person[v]].insert(map_person[u]);
}
vector<vector<int>> actions;
for(int i = 1;i<=q;i++){
int ty,u,v;scanf("%d %d %d",&ty,&u,&v);
actions.push_back({ty,u,v});
if(ty==1){
if(map_person.count(u) && map_person.count(v)) {
if (old_gra[map_person[u]].count(map_person[v])) {
gra[map_person[u]].erase(map_person[v]);
gra[map_person[v]].erase(map_person[u]);
}
}
}
}
for(auto &[u,gu]:gra){
for(auto &v:gu){
p[find(u)] = find(v);
}
}
vector<string> res;
for(int i = actions.size()-1;i>=0;i--){
int ty = actions[i][0],u = actions[i][1],v = actions[i][2];
if(ty == 2){
if(map_person.count(u) && map_person.count(v)){
int mu = map_person[u],mv = map_person[v];
if(find(mu) == find(mv)){
res.push_back("Yes");
}
else res.push_back("No");
}else{
res.push_back("No");
}
}
else{
if(map_person.count(u) && map_person.count(v)){
int mu = map_person[u],mv = map_person[v];
if(old_gra[mu].count(mv)){
p[find(mu)] = find(mv);
}
}
}
}
for(int i = res.size()-1;i>=0;i--){
cout<<res[i]<<endl;
}
}
return 0;
}
