?咕咕了好久,AC怪終于想起來WA補題了,log2r終于開始嘗試寫博客啦QAQ
?(以下題目順序為自己做題時體感難度排序 )
F-對答案一時爽
Description
?
n
n
n道單選題,每題正確得 1 分,錯誤得0分,
?已知兩人每題的選項,求兩人可能的最大得分和、最小得分和,
Solution
?簽到,最小得分為0,最大得分在所有題目兩人中至少一人答案正確時取到,
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define MAXN 100+5
using namespace std;
inline int Fread(){
int val=0;
bool sign=false;
char ch;
while(~(ch=getchar()) && (ch<'0' || ch>'9') && (ch^'-'));
val=(sign=!(ch^'-'))?0:ch^48;
while(~(ch=getchar()) && (ch>='0' && ch<='9')) val=(val<<1)+(val<<3)+(ch^48);
return sign?~val+1:val;
}
char S[MAXN],T[MAXN];
int n,ans=0;
int main(){
n=Fread();
for(int i=1;i<=n;++i) scanf(" %c",&S[i]);
for(int i=1;i<=n;++i){
scanf(" %c",&T[i]);
ans+=(S[i]==T[i])?2:1;
}
printf("%d 0",ans);
return 0;
}
E-三棱錐之刻
Description
?求一個球心在棱長為 a a a的正三棱錐中心,半徑為 r r r的球與正三棱錐截交面的面積,
Solution
?高中立體幾何,所形成的四個截交面可能為空、圓、圓和正三角形截交、正三角形,分類討論即可,
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define pi acos(-1.0)
using namespace std;
int main(){
double a,r;
scanf("%lf%lf",&a,&r);
double dis1=sqrt(6.0)*a/12.0,dis2=sqrt(2.0)*a/4.0,dis3=sqrt(6.0)*a/4.0,ans=0.0;
if(r<dis1){
printf("0.00000");
return 0;
}
if(r<dis2) ans=pi*(r*r-dis1*dis1);
else if(r<dis3){
double r_=sqrt(r*r-dis1*dis1),dis=sqrt(3.0)*a/6.0,cur=3.0*(pi/3.0-acos(dis/r_))*r_*r_;
ans=cur+3.0*dis*sqrt(r_*r_-dis*dis);
}
else ans=sqrt(3.0)*a*a/4.0;
ans*=4.0;
printf("%.5lf",ans);
return 0;
}
B-括號
Description
?構造非空括號字串,恰好包含
k
k
k個不同合法括號對,
?字串長度
0
<
l
≤
1
e
5
,
0
≤
k
≤
1
e
9
0<l≤1e5,0≤k≤1e9
0<l≤1e5,0≤k≤1e9,
Solution
?1、 依次由
L
L
L個"(“和
R
R
R個”)“組成的字串構成的不同合法括號對數目為
L
×
R
L×R
L×R,
?2、 在上述序列中前
L
L
L個位置中第
m
m
m個位置插入一個”)",構成的不同合法括號對數目為
L
×
R
+
m
L×R+m
L×R+m,
?因此,只需找到
k
=
L
×
R
+
m
(
m
≤
L
,
L
+
R
+
1
≤
1
e
5
)
k=L×R+m(m≤L,L+R+1≤1e5)
k=L×R+m(m≤L,L+R+1≤1e5)即可,
為使
L
+
R
L+R
L+R盡可能小,且
m
≤
L
m≤L
m≤L,可取:
??
?最后特判一下 k = 0 k=0 k=0的情況,
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define MAXN 100+5
using namespace std;
inline int Fread(){
int val=0;
bool sign=false;
char ch;
while(~(ch=getchar()) && (ch<'0' || ch>'9') && (ch^'-'));
val=(sign=!(ch^'-'))?0:ch^48;
while(~(ch=getchar()) && (ch>='0' && ch<='9')) val=(val<<1)+(val<<3)+(ch^48);
return sign?~val+1:val;
}
int main(){
int k=Fread();
if(!k){
printf("(");
return 0;
}
int l=sqrt(k),r=k/l,mod=k-l*r;
for(int i=1;i<=mod;++i) printf("(");
printf(")");
for(int i=mod+1;i<=l;++i) printf("(");
for(int i=1;i<=r;++i) printf(")");
return 0;
}
I-限制不互素對的排列
Description
?構造
1
~
n
1~n
1~n的一種排列,使得恰好
k
k
k對相鄰兩數
g
c
d
gcd
gcd大于1,
?
2
≤
n
≤
1
e
5
,
0
≤
k
≤
n
/
2
2≤n≤1e5,0≤k≤n/2
2≤n≤1e5,0≤k≤n/2,
Solution
?
?1、 注意一下
k
≤
n
/
2
k≤n/2
k≤n/2的條件,可以把
1
~
n
1~n
1~n拆分成相鄰偶數、相鄰奇數和相鄰整數,
?2、
(
k
+
1
)
(k+1)
(k+1)個相鄰偶數構成k個不互素對,而相鄰奇數和相鄰整數之間
g
c
d
gcd
gcd均為1,因此先放置(k+1)個偶數,再按順序放置剩余的數即可,
k
<
n
/
2
k<n/2
k<n/2時均可用這種方式構造,
?3、 若
k
=
n
/
2
k=n/2
k=n/2,先按照
(
k
?
1
)
(k-1)
(k?1)的構造方式,然后取出排列中的6和3依次放到相鄰偶數排列后,不互素對增加了1,構造完成,
?4、 特判
n
<
6
n<6
n<6的情況即可,
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define MAXN 100000+5
using namespace std;
inline int Fread(){
int val=0;
bool sign=false;
char ch;
while(~(ch=getchar()) && (ch<'0' || ch>'9') && (ch^'-'));
val=(sign=!(ch^'-'))?0:ch^48;
while(~(ch=getchar()) && (ch>='0' && ch<='9')) val=(val<<1)+(val<<3)+(ch^48);
return sign?~val+1:val;
}
int main(){
int n=Fread(),k=Fread();
if(n==2) printf(k?"-1":"1 2");
else if(n==3) printf(k?"-1":"1 2 3");
else if(n==4) printf(k==2?"-1":k==1?"2 4 1 3":"1 2 3 4");
else if(n==5) printf(k==2?"-1":k==1?"2 4 1 3 5":"1 2 3 4 5");
else if(!k){
for(int i=1;i<=n;++i) printf("%d ",i);
}
else if(k==(n>>1)){
for(int i=1;i<=k;++i)
if(i^3) printf("%d ",i<<1);
printf("6 3 1 ");
for(int i=2;i<=k-1;++i) printf("%d ",i<<1^1);
if((k<<1)^n) printf("%d ",n);
}
else{
for(int i=1;i<=k+1;++i) printf("%d ",i<<1);
for(int i=0;i<=k;++i) printf("%d ",i<<1^1);
for(int i=(((k+1)<<1)^1);i<=n;++i) printf("%d ",i);
}
return 0;
}
A-串
Description
?求長度不超過
n
n
n,由小寫字母構成,洗掉或不洗掉部分字符后可得到"us"的字串個數,
?
2
≤
n
≤
1
e
6
2≤n≤1e6
2≤n≤1e6,答案對
1
e
9
+
7
1e9+7
1e9+7取模,
Solution
?遞推, f [ i ] f[i] f[i]表示長度為 i i i且符合題意的字串個數,考慮第 ( i + 1 ) (i+1) (i+1)位產生的方案數,
?1、 當前i位符合題意時,第
(
i
+
1
)
(i+1)
(i+1)位隨意填充,總方案數
26
×
f
[
i
]
26×f[i]
26×f[i],
?2、 考慮前i位不合題意,但前
(
i
+
1
)
(i+1)
(i+1)位符合題意,當且僅當前
i
i
i位含有’u’但不存在子序列"us",且第
(
i
+
1
)
(i+1)
(i+1)位為’s’,前
i
i
i位含有"u"的字串數目為
2
6
i
?
2
5
i
26^i - 25^i
26i?25i,前
i
i
i位存在子序列的字串數目為
f
[
i
]
f[i]
f[i],總方案數
2
6
i
?
2
5
i
?
f
[
i
]
26^i - 25^i-f[i]
26i?25i?f[i],
?因此,遞推方程: f [ i + 1 ] = 25 × f [ i ] + 2 6 i ? 2 5 i , f [ 2 ] = 1 f[i+1]=25×f[i]+26^i - 25^i,f[2]=1 f[i+1]=25×f[i]+26i?25i,f[2]=1
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
#define MAXN 1000000+5
#define MOD 1000000007
using namespace std;
inline int Fread(){
int val=0;
bool sign=false;
char ch;
while(~(ch=getchar()) && (ch<'0' || ch>'9') && (ch^'-'));
val=(sign=!(ch^'-'))?0:ch^48;
while(~(ch=getchar()) && (ch>='0' && ch<='9')) val=(val<<1)+(val<<3)+(ch^48);
return sign?~val+1:val;
}
inline ll qpow(ll x,ll k){
ll res=1ll;
for(int i=k;i;i>>=1,x=x*x%MOD)
if(i&1) res=res*x%MOD;
return res;
}
ll f[MAXN];
int main(){
int n=Fread();
ll ans=0ll;
f[2]=1;
for(int i=2;i<n;++i) f[i+1]=((f[i]*26)%MOD+qpow(26,i)%MOD-qpow(25,i)%MOD-f[i]%MOD+MOD)%MOD;
for(int i=1;i<=n;++i) ans=(ans+f[i])%MOD;
printf("%lld",ans);
return 0;
}
J-一群小青蛙呱蹦呱蹦呱
Description
?長度為
n
n
n的格子里放無窮多青蛙,第
i
i
i只青蛙路線為以1為首項,
p
[
i
]
p[i]
p[i]為公比的等比數列,其中
p
[
i
]
p[i]
p[i]為第
i
i
i大的素數,求
n
n
n個格子中所有未被占據格子編號的
l
c
m
lcm
lcm,
?
1
≤
n
≤
1.6
e
8
1≤n≤1.6e8
1≤n≤1.6e8,答案對
1
e
9
+
7
1e9+7
1e9+7取模,
Solution
?對每個未被占據的格子進行質因數分解,考慮每個質因子對答案的貢獻,
?質因子對 l c m lcm lcm的貢獻取決于質因子在未被占據的格子中最大次冪,
?每個未被占據的格子均有至少兩個質因子,因此,對于質因子2,其最大次冪為 l o g 2 [ n 3 ] log_2^{[\frac{n}{3}]} log2[3n?]?;對于其他質因子 p p p,其最大次冪為 l o g p [ n 2 ] log_p^{[\frac{n}{2}]} logp[2n?]?,
?最終答案 2 l o g 2 [ n 3 ] ∏ i = 2 k | p k ≤ n p i l o g p i [ n 2 ] 2^{log_{2}^{[\frac{n}{3}]}}\prod_{i=2}^{k|p_k≤n} p_i^{log_{p_i}^{[\frac{n}{2}]}} 2log2[3n?]?∏i=2k|pk?≤n?pilogpi?[2n?]??
?(有被題目名稱可愛到)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
#define MAXM 160000000+5
#define MAXN 10000000+5
#define MOD 1000000007
using namespace std;
inline int Fread(){
int val=0;
bool sign=false;
char ch;
while(~(ch=getchar()) && (ch<'0' || ch>'9') && (ch^'-'));
val=(sign=!(ch^'-'))?0:ch^48;
while(~(ch=getchar()) && (ch>='0' && ch<='9')) val=(val<<1)+(val<<3)+(ch^48);
return sign?~val+1:val;
}
bool vis[MAXM];
int cnt=0;
ll prime[MAXN];
inline void phi_prime(int n){
for(int i=2;i<=n;++i){
if(!vis[i]) prime[++cnt]=i;
for(int j=1;(j<=cnt && i*prime[j]<=n);++j){
vis[i*prime[j]]=true;
if(!(i%prime[j])) break;
}
}
return;
}
int main(){
int n=Fread();
phi_prime(n);
if(n<=5){
printf("empty");
return 0;
}
ll cur=1ll,ans=1ll;
while((cur<<1)<=n/3) cur=(cur<<1)%MOD;
ans=ans*cur%MOD;
for(int i=2;(prime[i] && prime[i]<=n);++i){
cur=1ll;
while(prime[i]*cur<=(n>>1)) cur=cur*prime[i]%MOD;
ans=ans*cur%MOD;
}
printf("%lld",ans);
return 0;
}
C-紅和藍
Description
?給定一顆樹,對樹的節點
1
~
n
1~n
1~n染紅色或藍色,使得紅色節點相鄰節點有且僅有一個紅色節點;藍色節點相鄰節點有且僅有一個藍色節點,
?
1
≤
n
≤
1
e
5
1≤n≤1e5
1≤n≤1e5
Solution
?1、 葉節點與其父節點為同色,
?2、 葉節點的父節點與其父節點的父節點為異色,
?3、 若將葉節點及其父節點洗掉,則其父節點的父節點成為新的葉節點,新葉節點必與新葉節點的父節點同色,
?因此,對于任意一個節點,當且僅當節點數目為奇數的子樹個數 ≤ 1 ≤1 ≤1時,該節點可以被染色,且該節點與其父節點顏色相反當且僅當該節點子樹大小為奇數,
?首先第一遍dfs預處理出以每個節點為根的子樹大小,順帶判斷無解的情況,然后第二遍dfs從根節點進行染色,
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define MAXN 100000+5
using namespace std;
inline int Fread(){
int val=0;
bool sign=false;
char ch;
while(~(ch=getchar()) && (ch<'0' || ch>'9') && (ch^'-'));
val=(sign=!(ch^'-'))?0:ch^48;
while(~(ch=getchar()) && (ch>='0' && ch<='9')) val=(val<<1)+(val<<3)+(ch^48);
return sign?~val+1:val;
}
struct Edge{
int u,v,nxt;
Edge(){nxt=-1;}
Edge(int u,int v):u(u),v(v){}
}g[MAXN<<1];
int cnt=-1,tot[MAXN],siz[MAXN],head[MAXN],col[MAXN];
inline void add_edge(int u,int v){
g[++cnt]=Edge(u,v);
g[cnt].nxt=head[u];
head[u]=cnt;
return;
}
bool dfs1(int u,int fa){
siz[u]=1;
for(int i=head[u];~i;i=g[i].nxt)
if(g[i].v!=fa){
if(!dfs1(g[i].v,u)) return false;
siz[u]+=siz[g[i].v];
if(siz[g[i].v]&1) ++tot[u];
}
return tot[u]<=1;
}
void dfs2(int u,int fa,int cur){
col[u]=cur;
for(int i=head[u];~i;i=g[i].nxt)
if(g[i].v!=fa) dfs2(g[i].v,u,siz[g[i].v]&1?cur:cur^1);
return;
}
int main(){
memset(head,0xff,sizeof head);
int n=Fread();
for(int i=1;i<n;++i){
int u=Fread(),v=Fread();
add_edge(u,v);
add_edge(v,u);
}
if((n&1) || (!dfs1(1,-1))){
printf("-1");
return 0;
}
dfs2(1,-1,0);
for(int i=1;i<=n;++i) printf(col[i]?"R":"B");
return 0;
}
D-點一成零
Description
?給定
n
×
n
n×n
n×n的
0
?
1
0-1
0?1方陣,每次操作把一個元素均為"1"的連通塊變為元素均為"0",
k
k
k次詢問,每次詢問把方陣中的某個元素變為"1",求每次詢問后把方陣變為0方陣的方案數,
?
n
≤
500
,
k
≤
1
e
5
n≤500,k≤1e5
n≤500,k≤1e5,強制在線,
Solution
?并查集維護每個連通塊大小,設連通塊數目為 N N N,第 i i i個連通塊大小為 s i z e i size_i sizei?,則方案數為 N ! ∏ i = 1 N s i z e i N!\prod_{i=1}^{N} size_i N!∏i=1N?sizei?,每次查詢時更新連通塊大小及數目,
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
#define MAXN (500+5)
#define MOD 1000000007ll
using namespace std;
inline int Fread(){
int val=0;
bool sign=false;
char ch;
while(~(ch=getchar()) && (ch<'0' || ch>'9') && (ch^'-'));
val=(sign=!(ch^'-'))?0:ch^48;
while(~(ch=getchar()) && (ch>='0' && ch<='9')) val=(val<<1)+(val<<3)+(ch^48);
return sign?~val+1:val;
}
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
int n,k,cnt,fa[MAXN*MAXN];
ll tot=1ll,fac[MAXN*MAXN],siz[MAXN*MAXN];
char s[MAXN][MAXN];
inline ll qpow(ll x,ll k){
ll res=1ll;
for(ll i=k;i;i>>=1,x=x*x%MOD)
if(i&1) res=res*x%MOD;
return res;
}
inline ll inv(ll x){
return qpow(x,MOD-2);
}
inline int Find(int x){
return x==fa[x]?x:fa[x]=Find(fa[x]);
}
inline void Union(int x,int y){
int rx=Find(x),ry=Find(y);
if(rx==ry) return;
tot=(tot*inv(siz[rx]))%MOD;
tot=(tot*inv(siz[ry]))%MOD;
fa[ry]=rx;
siz[rx]+=siz[ry];
tot=(tot*siz[rx])%MOD;
--cnt;
return;
}
inline bool judge(int x,int y){
return (~x) && (~y) && (x<n) && (y<n);
}
int main(){
n=Fread();
siz[0]=fac[0]=1ll;
for(int i=1;i<=n*n;++i){
fa[i]=i;
siz[i]=1ll;
fac[i]=fac[i-1]*i%MOD;
}
for(int i=0;i<n;++i){
scanf("%s",s[i]);
for(int j=0;j<n;++j)
if(!(s[i][j]^'1')){
++cnt;
for(int k=1;k<=4;++k){
int x=i+dx[k],y=j+dy[k];
if(!judge(x,y)) continue;
if(!(s[x][y]^'1')) Union(i*n+j,x*n+y);
}
}
}
k=Fread();
while(k--){
int x=Fread(),y=Fread();
if(s[x][y]^'1'){
s[x][y]='1';
++cnt;
for(int i=1;i<=4;++i){
int x_=x+dx[i],y_=y+dy[i];
if(!judge(x_,y_)) continue;
if(!(s[x_][y_]^'1')) Union(x*n+y,x_*n+y_);
}
}
printf("%lld\n",fac[cnt]*tot%MOD);
}
return 0;
}
?還剩下兩道題,一道不會的數學和一道大模擬,好像挺心把的(但不影響2048好玩hhh),應該有時間也不會去寫了,以上,

轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/256440.html
標籤:其他
上一篇:【模板】并查集
下一篇:仿頭條方形進度條
