自己還是太菜了，五個小時一個題也沒磕出來，還是隊友牛逼！...
Primality Test
先看這個題，可能一上去就被\(\frac{f(x)+f(f(x))}{2}\)向下取整吓住了，但仔細想想，\(f(x)\)與\(f(f(x))\)不是相鄰的質數嗎？那麼除2，向下取整，落點一定在兩者之間，那麼一定是合數。當然除了2,3的特例，這種特判下即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int T;cin>>T;
while(T--)
{
ll x;cin>>x;
if(x==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
Nun Heh Heh Aaaaaaaaaaa
為什麼這麼簡單的題，我當初看了那麼長的時間都沒看出來。
發現這個題的主要難點在于以目前i(c[i]='h')為結尾的字串為nunhehheh的方案數。我們大膽的設狀态，仔細考慮dp所代表的的集合，以及進行轉移。設f[i][j]表示前i位，其中第i位比對到nunhehheh的第j位的方案數。那麼若c[i]=s[j]，我們考慮枚舉上一個字元也就是s[j-1]出現的位置，f[i][j]=f[k][j-1].其中c[k]==s[j-1].但這種方法顯然是O(n^2)的。考慮轉移時，其實f[k][j-1],隻要是j-1即可，我們大可以用一個數組g[j]表示前i個字元中以某個點為j結尾的方案數。這樣的話轉移時就是O(1)的。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,P=998244353;
int T,n,f[N][12],cnt[N],g[12];
char c[N];
string s;
inline ll power(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1) ans=ans*x%P;
y>>=1;
x=x*x%P;
}
return ans%P;
}
inline void clear()
{
for(int i=0;i<=n+1;++i)
{
cnt[i]=0;
for(int j=0;j<=10;++j) f[i][j]=0;
}
memset(g,0,sizeof(g));
}
int main()
{
//freopen("1.in","r",stdin);
scanf("%d",&T);
s="2nunhehheh";
while(T--)
{
scanf("%s",c+1);
n=strlen(c+1);
clear();
for(int i=n;i>=1;--i)
{
cnt[i]=cnt[i+1];
if(c[i]=='a') cnt[i]++;
}
ll ans=0;
for(int i=1;i<=n;++i)
{
for(int j=9;j>=1;--j)//比對nunhehheh的每一位。
{
if(c[i]==s[j])
{
f[i][j]=g[j-1];
if(j==1) f[i][j]=1;
g[j]=(g[j]+f[i][j])%P;
if(j==9) ans=(ans+(ll)f[i][j]*(power(2,cnt[i])-1)%P)%P;
}
}
}
printf("%lld\n",ans);
}
return 0;
}
Monopoly
哎呀，這個題，感覺自己當時的思路已經很接近了，但是還是輸給了對于分類讨論的複雜性的恐懼，加上當時沒有一個完整的思路進行支撐，就棄療了。
首先我們設\(S\)為整個序列的和，\(s_i\)為第i位的字首和，那麼可以有這個式子\(s_i+kS=x(k>=0,1\leq i\leq n)\)，其中隻有\(S,x\)已知，我們做适當的調整，\(kS=x-s_i\)，這樣的話\(x-s_i\)必須是\(S\)的正整數（以及0）的倍數。那麼可以想到\(x,s_i\)對\(S\)同餘，也就是說餘數相同。這樣的話，我們可以對\(s_i\)根據對\(S\)的餘數進行分類，每次詢問的x隻在模數相同的一類中找。接下來考慮最小化\(i+k*n\)的值，這個時候我們可以讨論S>0，那麼為了滿足倍數的關系，必須滿足\(s_i\leq x\)，同時為了k足夠小，我們需要找到的\(s_i\)足夠大，(你把這個過程放在數軸上想)。也就是小于等于x的最大值。這不是二分嗎？我們再在每一類中進行排序，直接二分查找即可。接下來考慮S<0的情況，我們可以将序列中的每個數取反，再将x取反即可。注意當S=0時，系統會報錯，單獨讨論這種情況。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int T,n,m,num;
map<ll,int>mp;//map表示序列号。
map<ll,int>id[N];//餘數為i的數字為j的最小的i。
vector<ll>ve[N];
ll s[N];
inline void clear()
{
mp.clear();num=0;
for(int i=0;i<=n;++i)
{
s[i]=0;
id[i].clear();
ve[i].clear();
}
}
inline void solve()
{
mp[0]=0;
for(int i=1;i<=n;++i)
{
if(mp.find(s[i])==mp.end())
mp[s[i]]=i;
}
for(int i=1;i<=m;++i)
{
ll x;scanf("%lld",&x);
if(mp.find(x)==mp.end()) puts("-1");
else printf("%d\n",mp[x]);
}
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
clear();
for(int i=1;i<=n;++i)
{
ll x;scanf("%lld",&x);
s[i]=s[i-1]+x;
}
if(s[n]==0) {solve();continue;}
int op=1;if(s[n]<0) op=-1;
ll S=s[n]*op;
for(int i=0;i<=n;++i)
{
s[i]*=op;
ll ps=(s[i]%S+S)%S;
if(mp.find(ps)==mp.end()) mp[ps]=++num;
if(id[mp[ps]].find(s[i])==id[mp[ps]].end())
{
id[mp[ps]][s[i]]=i;
ve[mp[ps]].push_back(s[i]);
}
}
for(int i=1;i<=num;++i) sort(ve[i].begin(),ve[i].end());
for(int i=1;i<=m;++i)
{
ll x;scanf("%lld",&x);
x*=op;
if(x==0) {puts("0");continue;}
ll ps=(x%S+S)%S;
if(mp.find(ps)==mp.end()||ve[mp[ps]][0]>x) {puts("-1");continue;}
int j=mp[ps];
int k=upper_bound(ve[j].begin(),ve[j].end(),x)-ve[j].begin()-1;
ll so=ve[j][k];
ll ans=id[j][so]+((x-so)/S)*n;
printf("%lld\n",ans);
}
}
return 0;
}
Jumping Monkey
這個題當初還是隊友做出來的，自己主要是思路就沒想到那一塊去。由于每次從一個點出發一直跳，跳的最多的點的個數，想想其實問你的就是從這個點出發能跳到哪些點去，因為這些點我們可以按點權從小到大排序依次跳就完事了。當初困在了DP的思維上，想不出來好的轉移方式。後來看了看題解大大的做法，其實是圖論的知識吧，也不對就是思維的問題吧。我們考慮先将所有的點從小到大排序，依次考慮每個點能否到達點i，這樣點i一定比之前的點權大，隻要聯通即可。也就是重建立圖加邊的問題。考慮目前是一個空白的圖，我們依次将每個點加進去，考慮哪些點能到達目前這個點的話，就是連通塊的問題，若目前點能夠連到某個連通塊，則這個連通塊内的所有點都能到達這個點，那麼這些點的答案都加1.然後将這個點及其連到的點合并成一個新的連通塊即可。考慮整個需要我們維護的操作就是加上點，連通塊整個的值加1，合并連通塊。對于連通塊的做法，我隻會并查集，其實并查集就是維護連通塊是否聯通的問題，順帶記錄一些資訊。接下來就是這個題的精妙之處，我們發現，我們每次都是将一個連通塊的值都加1，我們可以将加進去的點i當做根節點，這樣的話那些連通塊的深度就加1，符合我們的要求，我們隻需要将點i向原本這個連通塊的根節點連邊即可。但這樣不就打亂了原本的土的結構了嗎？其實我們沒必要維護原本的土的結構，我們還需要在一個點i加進去之後，那些連通塊的點都可以加1就行。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n,f[N],a[N],b[N],d[N];
vector<int>son[N];
vector<int>bian[N];
map<pair<int,int>,bool>mp;
inline void clear()
{
mp.clear();
for(int i=1;i<=n;++i)
{
son[i].clear();
bian[i].clear();
f[i]=i;b[i]=i;
d[i]=0;
}
}
inline bool cmp(int x,int y) {return a[x]<a[y];}
inline int getf(int x) {return f[x]==x?x:f[x]=getf(f[x]);}
inline void dfs(int x)
{
for(auto y:bian[x])
{
d[y]=d[x]+1;
dfs(y);
}
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
clear();
for(int i=1;i<n;++i)
{
int x,y;scanf("%d%d",&x,&y);
son[x].push_back(y);
son[y].push_back(x);
}
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;++i)//依次加入每一個點。
{
int x=b[i];
for(auto y:son[x])//周遊i的每一個出邊
{
if(a[y]>a[x]) continue;
int t=getf(y);
if(mp.find({x,t})==mp.end())
{
mp[{x,t}]=1;
bian[x].push_back(t);
f[t]=x;
}
}
}
d[b[n]]=1;
dfs(b[n]);
for(int i=1;i<=n;++i) printf("%d\n",d[i]);
}
return 0;
}
Public Transport System
這個題當初也是想了好久沒出來，顯然因為如果\(a_i>a_{i-1}\)的話我們走目前的邊權的值就為\(a_i-b_i\)，這就使得我們必須記錄目前點的上一條邊是哪一條，想了想，其實所有的狀态數也不多，即m個狀态，畢竟隻有m條邊，每條邊對應一個狀态。但這個記錄就隻能用map實作，如果再跑dijkstra總的複雜度為O(mlognlogm)，m的範圍為\(1.2\times10^6\)，這算出來，\(6\times10^9\),好吧，我覺得出題人肯定就是專門卡這個暴力的....
瞅瞅題解大大的做法，原來是要重建立圖，又是建圖的問題，這種題不是隻在網絡流中考察嗎？好吧，這次确實拓了眼界。首先先将兩種邊分開，因為兩種邊權的圖，畢竟沒有單邊權的友善。考慮邊權\(a_i\)的邊，我們沒什麼限制條件，但對于邊權為\(a_i-b_i\)的邊，我們必須滿足一定條件，也就是前一條邊的\(a_i\)必須小于目前的\(a_i\)。我們可以發現由于一個之前的邊對應的可走的邊權為\(a_i-b_i\)的邊的\(a_i\)是在一個區間的，是以這就給我們的優化帶來了可能。（不是我說的，是題解說的。）具體的，我們可以這樣做：首先設d為目前點x的出度，我們将x拆分成d+1個點，\(（x_0,x_1,x_2,...,x_d）\),讓他們分别管理這些\(a_i-b_i\)出邊，其中所有邊權為\(a_i\)的邊由\(x_0\)管理。我們将x所有邊權為\(a_i-b_i\)的出邊按照\(a_i\)的從大到小排序，接下來将他們依次交給\(x_i\)管理(也就是\(x_i\)連排過序後為i的邊)。我們接下來i從0到d-1，從\(x_{i+1}\)向\(x_{i}\)連邊權為0的邊。這樣由于提前排過序，能從小的\(a_i\)走\(a_i-b_i\)的特殊邊，一定能從大的\(a_i\)走\(a_i-b_i\)的特殊邊。之後我們隻需要根據每個入邊找到相對應能走的最大的\(x_i\)，滿足它所管理的邊的\(a_i\)大于他的入邊即可。
具體的如下圖：
這樣，一共的點為n+m,一共的邊為2*m,即使m是\(1.2\times 10^6\)的資料量，我們跑dijkstra也完全沒有問題。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5+10;
int du[N],n,m,l[N],link[N],tot,vis[N];
ll dis[N];
//l[i]記錄每個點拆出來的d+1個點的第一個點的編号。
vector<int>son[N];//記錄每個點，對應的邊的編号。
struct bian{int x,y,A,B;}b[N];
struct wy{int y,v,next;}a[N<<1];
priority_queue<pair<ll,int> >q;
inline void add(int x,int y,int v)
{
a[++tot].y=y;a[tot].v=v;a[tot].next=link[x];link[x]=tot;
}
inline void clear()
{
tot=0;
for(int i=1;i<=n+m;++i) link[i]=0;
for(int i=1;i<=n;++i) son[i].clear(),du[i]=0;
}
inline bool cmp(int x,int y)
{
return b[x].A>b[y].A;
}
inline int find(int x,int A)//有一個ai的入邊應該連向點x中的哪個點
{
if(!du[x]||A>=b[son[x][0]].A) return l[x];//傳回x0的情況。
int L=0,R=du[x]-1;
while(L<R)//在x的邊中查找>A的最小的邊。
{
int mid=L+R+1>>1;
if(b[son[x][mid]].A>A) L=mid;
else R=mid-1;
}
return l[x]+L+1;
}
inline void dijkstra()
{
while(q.size()) q.pop();
for(int i=1;i<=n+m;++i)
{
dis[i]=1e18;
vis[i]=0;
}
dis[l[1]]=0;q.push({0,l[1]});
while(!q.empty())
{
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=link[x];i;i=a[i].next)
{
int y=a[i].y;
if(dis[x]+a[i].v<dis[y])
{
dis[y]=dis[x]+a[i].v;
q.push({-dis[y],y});
}
}
}
}
int main()
{
// freopen("1.in","r",stdin);
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
clear();
for(int i=1;i<=m;++i)
{
scanf("%d%d%d%d",&b[i].x,&b[i].y,&b[i].A,&b[i].B);
son[b[i].x].push_back(i);
du[b[i].x]++;
}
for(int i=1;i<=n;++i)
{
if(son[i].size())
sort(son[i].begin(),son[i].end(),cmp);
}
int num=0;
for(int i=1;i<=n;++i) //給每個點配置設定編号且處理内部的邊。
{
l[i]=++num; //l[i] - l[i]+du[i]是這個點所有拆出來的點的編号。
for(int j=du[i];j>=1;--j) add(l[i]+j,l[i]+j-1,0);
num+=du[i];
}
for(int i=1;i<=n;++i)//處理點i的所有邊
{
int js=son[i].size();
for(int j=0;j<js;++j)//枚舉i的所有出邊
{
int id=son[i][j];
int y=find(b[id].y,b[id].A);
add(l[i],y,b[id].A);//先處理邊權為ai的。
add(l[i]+j+1,y,b[id].A-b[id].B);
}
}
dijkstra();
for(int i=1;i<=n;++i)
{
if(dis[l[i]]==1e18) dis[l[i]]=-1;
printf("%lld",dis[l[i]]);
if(i!=n) printf(" ");
}
printf("\n");
}
return 0;
}