2021 CCPC 網絡選拔賽（重賽）
hdu 7127 Kanade Doesn’t Want to Learn CG
- 我是瞎子，全部了解成不包括終點，一直 W A WA WA
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
cin>>T;
while(T--)
{
double a,b,c;
cin>>a>>b>>c;
double x0,x1,y0,y1,y2;
cin>>x0>>x1>>y0>>y1>>y2;
double d=b*b-4*a*(c-y0);
if(d<=0)
{
cout<<"No"<<endl;
continue;
}
double xa=(-b-sqrt(b*b-4*a*(c-y0)))/(2*a), xb=(-b+sqrt(b*b-4*a*(c-y0)))/(2*a);
if(xa>xb) swap(xa,xb);
double yb=a*x1*x1+b*x1+c;
if(xa>=x0) // 不能從下往上
{
cout<<"No"<<endl;
}
else if(xb>x0 && xb<x1) // 第一種情況進球
{
cout<<"Yes"<<endl;
}
else if(xb>x1 && xb-x1<x1-x0 && yb<=y2 && yb>y0) // 第二種情況進球，注意yb=y2時也能反彈！！！
{
cout<<"Yes"<<endl;
}
else cout<<"No"<<endl;
}
return 0;
}
hdu 7129 Primality Test
分析：
- 即求相鄰兩質數除以二（向下取整）是否是質數
- 相鄰兩質數除以二的值肯定是介于兩者之間的一個數（就是合數了）
- 除了 ( 2 , 3 ) (2,3) (2,3) 要特判，其它輸出 " N O " "NO" "NO"
#include <bits/stdc++.h>
using namespace std;
signed main()
{
int T;
cin>>T;
while(T--)
{
long long n;
cin>>n;
if(n==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
hdu 7130 Monopoly
分析：
-
方法一：多條件排序 + + + 多條件二分
方法二：用 m a p map map 嵌套 v e c t o r vector vector 來實作方法一
-
将 a [ i ] a[i] a[i] 字首和得 s [ i ] s[i] s[i]，設 d = s [ n ] d=s[n] d=s[n]
即求是否存在 s [ i ] s[i] s[i]，使得： x = s [ i ] + k d ( k > = 0 ) x=s[i]+kd\ (k>=0) x=s[i]+kd (k>=0)
根據題目要求， a n s = k n + i ans=kn+i ans=kn+i , 取答案最小值
将上式同餘 d d d，即： x ≡ s [ i ] m o d d ( d > 0 ) x\equiv s[i]\bmod d\ (d>0) x≡s[i]modd (d>0)
- 根據 d d d 的值要分三類情況讨論：
-
d = 0 d=0 d=0
這種情況最簡單，直接判斷是否存在 s [ i ] = x s[i]=x s[i]=x 即可
-
d > 0 d>0 d>0
因為 d > 0 d>0 d>0，故滿足條件的 s [ i ] < = x s[i]<=x s[i]<=x
對于多個滿足條件的 s [ i ] s[i] s[i]，要找使 a n s ans ans 最小的那一個
可以想到是最大的，若有多個最大的，那就是出現在最前面的
-
d < 0 d<0 d<0
這種情況乍一想很複雜，取模都取不動了
可以通過取反的操作，将這種情況變成 d > 0 d>0 d>0 的情況
-
方法一：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
struct Node
{
int w,id,mo;
bool operator < (const Node &b)
{
return mo<b.mo || mo==b.mo && w<b.w || mo==b.mo && w==b.w && id>b.id;
//先按模數大小排，若相等再按字首和大小排，若還相等，再按下标大小排（下标下的在後面）
}
}s[N];
int binary(int l,int r,int k,int mo)
{
while(l<=r)
{
int mid=l+r>>1;
if(s[mid].mo>mo || s[mid].mo==mo && s[mid].w>k) // mo相等，傳回小于等于x的最後一個
r=mid-1;
else l=mid+1;
}
return r;
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
s[i].w=s[i-1].w+x;
s[i].id=i;
}
int d=s[n].w, fg=0;
if(d==0)
{
for(int i=1;i<=n;i++) s[i].mo=s[i].w;
}
else
{
if(d<0) //取反，注意是所有的都要取反
{
fg=1; d=-d;
for(int i=1;i<=n;i++) s[i].w=-s[i].w;
}
for(int i=1;i<=n;i++) s[i].mo=(s[i].w%d+d)%d;
}
sort(s+1,s+1+n);
//for(int i=1;i<=n;i++) cout<<s[i].mo<<' '<<s[i].id<<' '<<s[i].w<<endl;
while(m--)
{
int x;
cin>>x;
if(x==0) { cout<<"0"<<endl; continue; }
if(d==0)
{
int ans=binary(1,n,x,x);
if(s[ans].mo!=x) cout<<"-1"<<endl; //不存在
else cout<<s[ans].id<<endl;
}
else
{
if(fg) x=-x; //輸入的x也要取反，整體取反
int mo=(x%d+d)%d;
int p=binary(1,n,x,mo);
if(p==0) { cout<<"-1"<<endl; continue; }
// 當mo=0的時候，特殊情況p會跑到最前面，如果不特判直接GG，s[0].mo=0
if(s[p].mo!=mo) cout<<"-1"<<endl;
else cout<<(x-s[p].w)/d*n+s[p].id<<endl;
}
}
}
return 0;
}
方法二：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int s[N];
map <int, vector<pair<int,int> > >mp;
unordered_map <int,int> ma;
signed main()
{
int T;
scanf("%lld",&T);
while(T--)
{
mp.clear(); ma.clear();
int n,m;
scanf("%lld%lld",&n,&m);
s[0]=0;
for(int i=1;i<=n;i++)
{
int x;
scanf("%lld",&x);
s[i]=s[i-1]+x;
}
int d=s[n],fg=0;
if(d==0)
{
for(int i=1;i<=n;i++) if(!ma[s[i]]) ma[s[i]]=i;
while(m--)
{
int x;
scanf("%lld",&x);
if(x==0) printf("0\n");
else if(ma[x]) printf("%lld\n",ma[x]);
else printf("-1\n");
}
}
else
{
if(d<0)
{
d=-d; fg=1;
for(int i=1;i<=n;i++) s[i]=-s[i];
}
for(int i=1;i<=n;i++)
{
int mo=(s[i]%d+d)%d;
mp[mo].push_back({-s[i],i}); // s[i]要從大到小排，故先取反，這scz也是驚到我了
}
for(auto u=mp.begin();u!=mp.end();u++)
{
sort(u->second.begin(),u->second.end()); // id從小到大
}
while(m--)
{
int x;
scanf("%lld",&x);
if(x==0) { printf("0\n"); continue; }
if(fg) x=-x;
int mo=(x%d+d)%d;
if(mp[mo].size()==0) printf("-1\n");
else
{
pair <int,int> t={-x,0}; // 根s[i]同步取反
int p=lower_bound(mp[mo].begin(),mp[mo].end(),t)-mp[mo].begin();
// 傳回大于等于-x的第一個
if(p==mp[mo].size()) printf("-1\n"); //沒找到
else
{
int ans=mp[mo][p].second;
ans+=(x+mp[mo][p].first)/d*n;
printf("%lld\n",ans);
}
}
}
}
}
return 0;
}
hdu 7131 Nun Heh Heh Aaaaaaaaaaa
分析：
- 線性 D P + DP + DP+ 字尾和
- 字尾和維護 a a a 的數量，假設 k k k 個 a a a 的任意選擇，即： ∑ i = 1 k C k i = 2 k − 1 \sum_{i=1}^{k}C_k^i=2^k-1 ∑i=1kCki=2k−1
-
維護一定順序出現的一串序列，典型的線性 D P DP DP
d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 j j j 位比對到第 i i i 個字首的方案數
若目前位為要比對的字首： d p [ i ] [ j ] = d p [ i ] [ j − 1 ] + d p [ i − 1 ] [ j − 1 ] dp[i][j]=dp[i][j-1]+dp[i-1][j-1] dp[i][j]=dp[i][j−1]+dp[i−1][j−1]
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
const int N=1e5+5, mo=998244353;
int f[N];
char s[N],ss[15]=" nunhehheh";
int sum[N];
int n,ans;
int dp[12][N];
signed main()
{
f[0] = 1;
for(int i=1;i<=1e5;i++) f[i]=(f[i-1]*2)%mo;
int T;
for(int i=0;i<=1e5;i++) dp[0][i]=1;
cin>>T;
while(T--)
{
scanf("%s", (s + 1));
n=strlen(s+1);
sum[n+1]=0;
for(int i=n;i;i--)
{
sum[i]=sum[i+1];
if(s[i]=='a') sum[i]++;
}
for(int i=1;i<=9;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i][j-1]; // 繼承
if(s[j]==ss[i]) dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%mod;
}
}
ans=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='h') ans = (ans+1ll*((dp[9][i]-dp[9][i-1]+mod)%mod)*((f[sum[i+1]]-1+mod)%mod)%mod)%mod;
// dp[9][i]-dp[9][i-1]表示目前位(第i位)的方案數
}
cout<<ans<<endl;
}
return 0;
}
hdu 7135 Bigraph Extension
分析：
- 構造一個 2 n 2n 2n 的環
- 兩個集合之間連邊，且要求從 A A A 集合任意一點到 B B B 集合任意一點（可能會有多條邊），要求最長的邊 l e n > n len>n len>n
-
考慮将這個二分圖展開來看，會是一個連通塊，且一條邊上的兩端點分别屬于兩個集合
要使 l e n > n len>n len>n，那這個連通塊必然是由多個環組成的（鍊上肯定存在 l e n < = n len<=n len<=n 的情況）
又要使添的的邊最少，是以構造一個 2 n 2n 2n 的環即可
- 具體構圖方法：并查集 + + + 環的性質（每個點的度都為 2 2 2 ）
- 按字典序的話，就從點 1 1 1 ~ n n n 逐一構造即可
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int du[N],f[N];
int fd(int k) { return f[k]==k ? k : f[k]=fd(f[k]); }
vector <pair<int,int> > g;
signed main()
{
ios_base::sync_with_stdio(0);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) du[i]=du[i+n]=0, f[i]=i, f[i+n]=i+n;
g.clear();
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
du[u]++;
du[v+n]++;
f[v+n]=u;
}
int st=1;
for(int i=1;i<=n;i++)
{
for(int j=st;j<=n;j++)
{
if(du[j+n]<2)
{
int x=fd(i), y=fd(j+n);
if(x!=y)
{
du[i]++; du[j+n]++;
f[y]=x;
g.push_back({i,j});
}
}
if(du[i]==2) break;
if(du[st+n]==2) st++;
}
}
for(int i=1;i<=n;i++)
{
if(du[i+n]==1)
{
g.push_back({n,i});
break;
}
}
cout<<g.size()<<endl;
for(auto ans : g) cout<<ans.first<<' '<<ans.second<<endl;
}
return 0;
}
hdu 7136 Jumping Monkey
分析：
- 并查集+重構樹
-
可以想到 B F S BFS BFS 去周遊，每次從目前權值最大點出發跑一遍 B F S BFS BFS，經過的點的 d e p + + dep++ dep++
然後，便将權值最大點去掉，繼續重複上一個操作
但是，這樣顯然會 T T T（代碼見下文）
-
考慮如何優化？（從比賽開始到結束，也沒想出怎麼優化）
n n n 遍 B F S BFS BFS ，過程有很多步是重複的
如果這棵樹以權值最大點為根，從上到下的權值是遞減的，那答案就是每個節點的深度（這就很 n i c e nice nice ）
-
如何重構這棵樹？
考慮普遍情況和上述的特殊情況，差別在哪？
差別就在于：普遍情況并非嚴格遞減的
要有一種重構的方法，将這棵樹變成特殊情況的，且還不會影響最終答案
-
重構方法
按點權從小到大枚舉結點 u u u ，并将 u u u 作為所有與 u u u 相連的（已經枚舉過的）連通塊的根（這裡要用并查集維護）
進而建立一棵新樹，每個結點的深度（根的深度為 1 1 1 ）即是答案。
重構方法的正确性，多畫幾張圖就能了解了~
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
return f*x;
}
struct Node
{
int next,to;
}e[N<<1];
int head[N],tot;
inline void add(int u,int v)
{
e[++tot].next=head[u];
e[tot].to=v;
head[u]=tot;
}
struct graph
{
int w,id;
bool operator <(const graph &a) const { return w<a.w; }
}b[N];
int f[N];
int fd(int k) { return f[k]==k ? k : f[k]=fd(f[k]); }
vector <int> g[N];
int dep[N];
void dfs(int u)
{
for(auto v : g[u])
{
dep[v]=dep[u]+1;
dfs(v);
}
}
int vis[N];
signed main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
n=read();
tot=0;
for(int i=1;i<=n;i++)
{
f[i]=i; g[i].clear(); dep[i]=vis[i]=head[i]=0;
}
for(int i=1;i<n;i++)
{
int u,v;
u=read(); v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
{
b[i].w=read();
b[i].id=i;
}
sort(b+1,b+1+n);
vis[b[1].id]=1;
for(int i=2;i<=n;i++)
{
int u=b[i].id;
for(int i=head[u]; i ;i=e[i].next)
{
int v=e[i].to;
if(vis[v])
{
int y=fd(v); // 找到連通塊的祖宗
f[y]=u;
g[u].push_back(y); // 重構樹
}
}
vis[u]=1; //要維護的集合裡加入該點
}
dep[b[n].id]=1;
dfs(b[n].id);
for(int i=1;i<=n;i++) printf("%d\n",dep[i]);
}
return 0;
}
BFS (T了的)
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
return f*x;
}
struct Node
{
int next,to;
}e[N<<1];
int head[N],tot;
inline void add(int u,int v)
{
e[++tot].next=head[u];
e[tot].to=v;
head[u]=tot;
}
struct graph
{
int w,id;
bool operator <(const graph &a) const { return w>a.w; }
}b[N];
int dep[N];
int vis[N],vis1[N];
signed main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
n=read();
tot=0;
for(int i=1;i<=n;i++)
{
dep[i]=vis[i]=head[i]=0;
}
for(int i=1;i<n;i++)
{
int u,v;
u=read(); v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
{
b[i].w=read();
b[i].id=i;
}
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) vis1[j]=0;
queue <int> q;
q.push(b[i].id);
dep[b[i].id]+=1;
vis[b[i].id]=1; // 去掉目前點
vis1[b[i].id]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int j=head[u]; j ;j=e[j].next)
{
int v=e[j].to;
if(vis[v] || vis1[v]) continue;
dep[v]+=1;
q.push(v);
vis1[v]=1;
}
}
}
for(int i=1;i<=n;i++) printf("%d\n",dep[i]);
}
return 0;
}
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)