头像

SherlockOuO




离线:2小时前


最近来访(30)
用户头像
雷霆尬拔
用户头像
宇宙_5
用户头像
Garde
用户头像
一天不A浑身难受
用户头像
daftchris
用户头像
好孩子都会写代码
用户头像
RyanMoriarty
用户头像
BT7274
用户头像
icebreaker
用户头像
HH123_
用户头像
初夏雾雨
用户头像
acwing_wkp
用户头像
沙漠之狐
用户头像
翩竹
用户头像
姚军
用户头像
好好吃饭好好睡觉
用户头像
j_1
用户头像
Pluviophile
用户头像
教练....我想学算法
用户头像
维Cboy


题目描述

如果一个客户拥有多条记录,则需要将这些记录进行合并,每人只保留一条记录,去记录他的全部有效号码。
如果一个客户记录的多个电话号码完全相同,则只保留一个作为有效号码,其余的全部视为无效号码。
如果一个客户记录的两个不同电话号码 a 和 b 满足 a 是 b 的后缀,则号码 a 视为无效号码

第一反应就是用trie 不过考试时没有调试出。ToT

让求后缀,不是很好求,就转化为前缀,逆序就可以,然后这里使用trie来存储
然后用哈希表来 存储名字和电话号码。

记得注意:
- 同一个人可能会重复出现
- 不要犯低级语言错误

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <map>

using namespace std;

const int N = 100;


struct trie{
  int nxt[1000][10],cnt;
  bool exist[1000];

  void insert(string s){
    int l = s.size();
    int p = 0;
    for(int i=0;i<l;i++){
      int c = s[i]-'0';
      if(!nxt[p][c]) nxt[p][c] = ++cnt;
      p=nxt[p][c];
      // false on the path
      exist[p]=0;
    }
    for(int i=0;i<10;i++)
      if(nxt[p][i]) {
        exist[p]=0;
        return;
      }
    exist[p]=1;
  }

  bool find(string s){
    int l = s.size();
    int p = 0;
    for(int i=0;i<l;i++){
      int c = s[i]-'0';
      if(!nxt[p][c]) return 0;
      p = nxt[p][c];
    }
    return exist[p];
  }

}tree[N];




int main(){

  int n;
  cin>>n;
  unordered_map<string,vector<string>> mp;
  unordered_map<string,int> mm;
  while(n--){
    string name;
    int cnt;
    cin>>name>>cnt;
    if(!mm.count(name))
      mm[name]=n;
    vector<string> strs;

    if(mp.count(name)){
      strs = mp[name];
    }

    for(int i=0;i<cnt;i++){
      string phone;
      cin>>phone;
      // cout<<"show phone"<<phone<<endl;
      reverse(phone.begin(),phone.end());
      auto t = mm.find(name);
      tree[t->second].insert(phone);
        strs.push_back(phone);
    }
    mp[name]=strs;
    // cout<<"-----"<<endl;
    // for(auto x:mm){
    //   cout<<x.first<<" "<<x.second<<endl;
    // }
    // cout<<"-----"<<endl;
  }

  cout<<mp.size()<<endl;
  for(auto x:mp){

    vector<string> numbers;
    numbers.clear();
    cout<<x.first<<" ";
    auto phones = x.second;
    string nm = x.first;
    auto t = mm.find(nm);
    // cout<<t->first<<endl;
    int no = t->second;
    sort(phones.begin(),phones.end());
    phones.erase(unique(phones.begin(),phones.end()),phones.end());
    for(auto p:phones){
        string tmp = p;
        // puts("");
      // cout<<"no "<<no<<endl;
      if(tree[no].find(p)){
        // puts("");
        // cout<<"p "<<p<<" "<<tree[no].find(p)<<endl;
        numbers.push_back(p);
        // cout<<"debug putin "<<p<<endl;
      }
    }
    // for(auto s:numbers){
    //   cout<<"debug get "<<s<<endl;
    // }
    // sort(numbers.begin(),numbers.end());
    cout<<numbers.size()<<" ";
    for(auto p:numbers){
      reverse(p.begin(),p.end());
      cout<<p<<" ";
    }
    puts("");
  }

  return 0;
}


活动打卡代码 AcWing 125. 耍杂技的牛

SherlockOuO
1个月前

此题的关键在于 想出 wi + si < wi+1 + si+1
进而推导出 按照两数之和的顺序排序 得到的结果最小

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define x first
#define y second
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

vector<pii> v;
// const int N = 5*1e4;
// int w[N],s[N];
int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    int w,s;
    cin>>w>>s;
    v.push_back({s+w,s});
  }

  sort(v.begin(),v.end());

  LL ans = -1e9, sum =0;
  for(int i=0;i<n;i++){
    int k = v[i].y, w = v[i].x - k;
    ans = max(ans, sum-k);
    sum+=w;
  }

  printf("%lld\n",ans);

  return 0;
}


活动打卡代码 AcWing 104. 货仓选址

SherlockOuO
1个月前

排序 中位数有着全局最优性 所以以中位数来算就能得到最优的选址

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
int a[100010];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    ll res =0;
    for(int i=0;i<n;i++)
        res+=abs(a[i]-a[n/2]);
    cout<<res<<endl;
    return 0;
}



活动打卡代码 AcWing 913. 排队打水

SherlockOuO
1个月前

贪心 让最墨迹的人最后

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e5+10;
int a[N];
int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a,a+n);
  long long res =0;
  for(int i=0;i<n;i++){
    res+=(a[i]*(n-i-1));
  }

  printf("%lld\n",res);

  return 0;

}


活动打卡代码 AcWing 907. 区间覆盖

SherlockOuO
1个月前
#include <iostream>
#include <algorithm>
#include <vector>
#define x first
#define y second

using namespace std;
int n,dx,dy;
typedef pair<int,int> pii;
vector<pii> vii;


int main(){
  scanf("%d%d",&dx,&dy);
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    vii.push_back({a,b});
  }
  // 按左端点排序
  sort(vii.begin(),vii.end());

  int res = 0;
  bool flag = false;
  for(int i=0;i<n;i++){
    int j = i,r= -2e9;
    // 一个一个往右扩张 
    // 保证每个扩张的区间都是包含了左端点的是为了取的最小覆盖数目
    while(j<n&&vii[j].x<=dx){
      r = max(vii[j].y,r);
      j++;
    }
    // 如果连一个也扩张不了 则flag=0
    if(r<dx){
      flag=0;
      break;
    }
    res++;
    if(r>=dy){
      flag = 1;
      break;
    }
    dx=r;
    i = j-1;
  }

  if(flag) printf("%d\n",res);
  else printf("-1\n");

  return 0;
}


活动打卡代码 AcWing 906. 区间分组

SherlockOuO
1个月前

一开始 拿右端点开始排序 翻车了 去看了下题解 发现大多都是用左端点来写的

用左端点来写 为的是在确定分组的时候 不用瞻前顾后考虑多种情况,而只需要往前合并。
类似于处理将题目变成单调的来计算

个人见解都放代码里了

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
vector<pii> a;
int n;
int main(){
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    int x,b;
    scanf("%d%d",&x,&b);
    //按照左端点来排序
    a.push_back({x,b});
  }
  sort(a.begin(),a.end());
  // 存当前所有组的最大右端点
  // ?为什么存的是组最大右端点呢?
  // 因为枚举的是区间左端点,当区间左端点的值 大于了前面区间组的最大右端点时 就需要新开一个组
  // 由于是左端点是从小到大排序的 所以不会产生后面的区间跑到前面分组的情况
  priority_queue<int,vector<int>,greater<int>> hp;
  for(int i=0;i<n;i++){
    // 如果 分组为空 或者 分组间有交叉就创建新的分组
    if(hp.empty()||a[i].x <= hp.top()){
      hp.push(a[i].y);
    }else{
      // 分组扩张 删掉原来的组
      hp.pop(); 
      hp.push(a[i].y);
    }
  }
  printf("%d\n",hp.size());
  return 0;
}



SherlockOuO
2个月前

考研感觉要G了 所以 准备春招找个工作,大家给点建议啦。谢谢各位!



活动打卡代码 AcWing 97. 约数之和

SherlockOuO
2个月前
#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 9901;

int A,B;

unordered_map<int,int> primes;

void divide(int n){
  for(int i=2; i<=n/i;i++){
    if(n%i==0){
      while(n%i == 0){
        primes[i]++;
        n/=i;
      }
    }
  }
  if(n>1){
    primes[n]++;
  }
}

int qmid(int a,int b){
  int res = 1;
  while(b){
    if(b&1){
      res = (LL) res * a % mod;
    }
    a = (LL)a*a%mod;
    b>>=1;
  }
  return res;
}


int main(){
  cin>>A>>B;

  divide(A);

  int res = 1;
  for(auto it:primes){
    //p是质因子,k是质因子的次数
   int p = it.first, k = it.second *B;
   //res要乘上每一项
   if((p-1)%mod == 0){
     res = (LL)res*(k+1)%mod;
   }else{
     res = (LL)res *(qmid(p,k+1)-1)%mod*qmid(p-1,mod-2)%mod;
   }
  }
  if(!A) res = 0;
  cout << (res%mod + mod)%mod<<endl;

  return 0;
}






SherlockOuO
3个月前
#include <algorithm>
#include <cstdio>
using namespace std;
struct edge {
  int v, next;
} e[6005];
int head[6005], n, cnt, f[6005][2], ans, is_h[6005], vis[6005];
void addedge(int u, int v) {  //建图
  e[++cnt].v = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}
void calc(int k) {
  vis[k] = 1;
  for (int i = head[k]; i; i = e[i].next) {  // 枚举该结点的每个子结点
    if (vis[e[i].v]) continue;
    calc(e[i].v);
    f[k][1] += f[e[i].v][0];
    f[k][0] += max(f[e[i].v][0], f[e[i].v][1]);  //转移方程
  }
  return;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &f[i][1]);
  for (int i = 1; i < n; i++) {
    int l, k;
    scanf("%d%d", &l, &k);
    is_h[l] = 1;
    addedge(k, l);
  }
  for (int i = 1; i <= n; i++)
    if (!is_h[i]) {  // 从根结点开始DFS
      calc(i);
      printf("%d", max(f[i][1], f[i][0]));
      return 0;
    }
}


活动打卡代码 AcWing 95. 费解的开关

SherlockOuO
4个月前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>

using namespace std;

int dx[5] = {0,0,-1,1,0};
int dy[5]={-1,1,0,0,0};

char a[10][10],backup[10][10];
int n;

void turn(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        int tx = x+dx[i];
        int ty = y +dy[i];
        if(tx<0||ty<0||tx>=5||ty>=5)
            continue;
        a[tx][ty]^=1;
    }
}

int work(){
    int res=INT_MAX;
    for(int c=0;c < 1<<5;c++){
        memcpy(backup,a,sizeof a);
        int steps=0;
        //第一行所有的按法都枚举一遍,无论是开还是关,依次来得到解的范围
        for(int i=0;i<5;i++)
            if(c>>i&1){
                steps++;
                turn(0,i);
            }
        //美剧0——3行,按1——4行 只按0的下面的位置
        for(int i=0;i<4;i++){
            for(int j=0;j<5;j++){
                if(a[i][j]=='0'){
                    steps++;
                    turn(i+1,j);
                }
            }
        }
        int flag=1;
        //判断是否全亮
        for(int i=0;i<5;i++){
            // cout<<a[4][i]<<" ";
            if(a[4][i]=='0'){
                flag=0;
                break;
            }
        }
        if(flag)
            res=min(res,steps);
        memcpy(a,backup,sizeof backup);
    }
    if(res>6) return -1;
    else
        return res;
}


int main()
{
    scanf("%d",&n);
    while(n--){
        for(int i=0;i<5;i++)
            cin>>a[i];
         int res = work(); 
        cout<<res<<endl;
    }


    return 0;
}