胖爺XP的hu測 T3.程式（提答）

版權屬于XP，想要引用此題（包括題面）的朋友請聯系部落客

分析：

為什麼我要在blog裡寫提答題：感覺這次的提答比較好，考核的知識點很好

dada們就當玩笑看看吧

一道一道看

program1

#include<bits\stdc++.h>
using namespace std;
int getseed(char *s)
{
    int seed=;
    int len=strlen(s);
    for(int i=;i<len;i++)
    seed=seed*+s[i]-'a'+;
    return seed;
}
int n;
char s[][];
map<int,int>ma;
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    scanf("%s",s[i]);
    int ans=n;
    for(int i=;i<=n;i++)
    {
        int sed=getseed(s[i]);
        if(ma[sed]) ans--;
        else ma[sed]++;
    }
    cout<<ans;
}
           

int自然溢出的hash，相當于% 232 2 32

最簡單的，我們考慮找到一個和 ′a′ ′ a ′ 同餘的字元串

那麼這個字元串的hash值應該是 232+1=4294967297 2 32 + 1 = 4294967297

把這個數轉成27進制即可

（注意由于字元串中沒有表示0的字元，是以如果在轉換的時候出現了0，就需要換一個數，然而出題人良心并不存在這個問題）

//可行解

a
kbhsymw
           

（當然還可以暴力構造）

//可行解

enqwlth
ppzpkgc
           

program2

#include<bits\stdc++.h>
using namespace std;
typedef pair<int,int> pi;
pi getseed2(char *s)
{
    long long seed1=,seed2=;
    int len=strlen(s);
    for(int i=;i<len;i++)
    {
        seed1=seed1*+s[i]-'a'+;
        seed1%=;
        seed2=seed2*+s[i]-'a'+;
        seed2%=;
    }
    return pi(seed1,seed2);
}
int n;
char s[][];
map<pi,int>mp;
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    scanf("%s",s[i]);
    int ans=n;
    for(int i=;i<=n;i++)
    {
        pi sed=getseed2(s[i]);
        if(mp[sed]) ans--;
        else mp[sed]++;
    }
    cout<<ans;
}
           

雙hash

簡單的，我們考慮如何構造一個和 ′a′ ′ a ′ hash相同的字元串卡掉上面的程式

我們需要找到一個%兩個模數答案都等于0的數字（+1就可以與 ′a′ ′ a ′ 同餘了）

換句話說，我們需要找到兩個模數的共同倍數： lcm l c m 即可（直接把兩個模數乘起來）

轉換成27進制

（還是注意由于字元串中沒有表示0的字元，是以如果在轉換的時候出現了0，就需要換一個數，然而出題人良心并不存在這個問題）

//可行解

a
cljjdkjejxuf
           

program3

#include<bits\stdc++.h>
using namespace std;
int num;
int main()
{
    scanf("%d",&num);
    int p=;
    int sz=sqrt(num);
    for(int i=;i<sz;i++)
    if(num%i==) p=;
    if(p) puts("Yes");
    else puts("No");
}
           

顯然質數平方就可以卡掉這個代碼

program4

#include<bits\stdc++.h>
using namespace std;
int num;
int quickpow(int x,int p)
{
    int ans=;
    for(int t=p-;t;t>>=,x=x*x%p)
    if(t&) ans=ans*x%p;
    return ans;
}
int gcd(int x,int y)
{
    return y==?x:gcd(y,x%y);
}
int main()
{
    scanf("%d",&num);
    int p=;
    for(int i=;i<num;i++)
    if(quickpow(i,num)!=&&gcd(i,num)==) p=;
    if(p) puts("Yes");
    else puts("No");
}
           

考察僞素數

我們naive的掃一遍即可

program5

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int,int> IntPair;
typedef vector<IntPair> VectorIntPair;
#define INF 1000000000
int i,j,u,V,n,w,Q,time_up,s,t;
vector<VectorIntPair> AdjList;
bool change;
int main() {
  scanf("%d",&V);
  AdjList.assign(V,VectorIntPair());
  for(i=;i<V;i++) {
    scanf("%d",&n);
    while(n--){
      scanf("%d%d",&j,&w);
      AdjList[i].push_back(IntPair(j,w));
    }
  }
  time_up=;
  scanf("%d",&Q);
  while(Q--){
    scanf("%d%d",&s,&t);
    vector<int>dist(V,INF);
    dist[s]=;

    for (i=;i<V-;i++) {
      change=false;
      for (u=;u<V;u++)
        for (j=;j<(int)AdjList[u].size();j++){
          time_up++;
          if (time_up>){
            printf("TLE");
            return ;
          } 
          IntPair v=AdjList[u][j];
          if (dist[u]+v.second<dist[v.first]){
            dist[v.first]=dist[u]+v.second;
            change=true;
          }
        }
      if (!change)
        break;
    }
    printf("%d\n",dist[t]);
  }
  printf("time_up=%d\n",time_up);
  return ;
}
           

bellman ford算法

這題的字元限制比較寬松，觀察程式特點可以看出：

for (j=0;j<(int)AdjList[u].size();j++)

這個程式是從0~n-1依次枚舉邊進行松弛，然後如果有一次沒有松弛操作則退出

那麼我們可以利用這個缺陷，第一次在 n−1 n − 1 松弛，第二次在 n−2 n − 2 松弛，以此類推

然後讓程式把大量無用操作放在前面節點的重邊和自環上

實作方式：從0~299依次連最短路，然後詢問的時候從299詢問到0（其中加上一些重邊）

program6

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> IntPair;
typedef vector<IntPair> VectorIntPair;
#define INF 1000000000
int i,j,V,n,w,time_up,Q,s,t,d,u;
vector<VectorIntPair> AdjList;
int main() 
{
  scanf("%d",&V);
  AdjList.assign(V,VectorIntPair());
  for (i=;i<V;i++) {
    scanf("%d",&n);
    while(n--){
      scanf("%d%d",&j,&w);
      AdjList[i].push_back(IntPair(j, w));
    }
  }
  time_up=;
  scanf("%d",&Q);
  while(Q--){
    scanf("%d%d",&s,&t);
    vector<int>dist(V,INF);
    dist[s]=;
    priority_queue<IntPair,vector<IntPair>,greater<IntPair> >pq;
    pq.push(IntPair(,s));
    while(!pq.empty()){
      time_up++;
      if (time_up>){
        printf("TLE");
        return ;
      }
      IntPair front=pq.top();pq.pop();
      d=front.first;u=front.second;
      if (d==dist[u]) {
        for(j=;j<(int)AdjList[u].size();j++) {
          IntPair v=AdjList[u][j];
          if (dist[u]+v.second<dist[v.first]) {
            dist[v.first]=dist[u]+v.second;
            pq.push(IntPair(dist[v.first],v.first));
          }
        }
      }
    }
    printf("%d\n",dist[t]);
  }

  printf("time_up=%d\n",time_up);
  return ;
}
           

堆優dij，在 n<=300 n <= 300 的情況下很難卡

然而ta畢竟是一個dijkstra，我們可以通過設定負權邊的方式來卡

可以看到，dijkstra面對這種圖出現了重複的無用操作

（不同顔色代表不同的更新路徑）

可以發現在出現若幹以上圖嵌套的情況下，可以把dij的效率卡成指數級

但是我們有字元限制

我們可以分析一下，把10組詢問問滿，需要21個字元，點數量需要1個

建構一個這樣的圖需要兩個點，三條邊，邊占兩個字元，點占一個字元，共計8個，最後還有一個點的出度為0，再占一個字元

143-21-1-1=120 正好可以建構15組

但是當你愉快地建構了15組以後，你發現time_up≈980000

我們進行微調，去掉4組詢問，改為加一組圖就可以了

//可行解

  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -
  -  -
  -


 
 
 
 
 
 
           

彩蛋