K：Co-prime Permutation
??簽到題，一個常見的套路：相鄰兩個數的最大公因子是1.這個結論的出來以后，除了
k
=?
0
k\not =0
k?=0的情況時Impossible，其他情況都可以通過將原本下標和值相等的序列右移一位來得到正確答案，
L：Let’s Play Curling
??簽到題，題目想求解的是，在給定
c
c
c的情況下，能夠找到多少個
a
i
a_i
ai?，使得對于所有的
b
i
b_i
bi?，都有
∣
a
i
?
c
∣
<
∣
b
i
?
c
∣
\big|a_i-c\big |<\big|b_i-c\big|
∣∣?ai??c∣∣?<∣∣?bi??c∣∣?.
??使用貪心的策略：兩個
b
i
b_i
bi?之間的
a
i
a_i
ai?的個數就是我們的答案，如果想在更大的區間（
b
i
b_i
bi?和
b
i
+
2
b_{i+2}
bi+2?）內找到一個
c
c
c，使得在
b
i
b_i
bi?兩邊的
a
i
a_i
ai?都能滿足條件，顯然是不現實的，這樣還是會把大區間分解成兩個小區間，我們直接使用上述的貪心策略即可，在具體求解的時候，可以考慮將陣列
a
a
a和
b
b
b去重，并對陣列
a
a
a中出現的元素計數（不能直接采用陣列的方式），
#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=1e5+100;
int a[maxn],b[maxn];
map<int,int> mp;
int main()
{
close;
int T;cin>>T;
while(T--)
{
int n,m;cin>>n>>m;
mp.clear();
for(int i=0;i<n;++i) cin>>a[i],mp[a[i]]++;
for(int j=1;j<=m;++j) cin>>b[j];
sort(a,a+n);int size=unique(a,a+n)-a;
sort(b+1,b+m+1);int p=0;int s=unique(b+1,b+m+1)-b-1;
b[s+1]=1e9+100;b[0]=0;
int ans=0;
for(int i=1;i<=s+1 && p<size;++i)
{
int tmp=0;
while(p<size && a[p]<b[i]) tmp+=mp[a[p]],p++;
if(tmp>ans) ans=tmp;
if(a[p]==b[i]) p++;
}
if(ans==0) cout<<"Impossible"<<endl;
else cout<<ans<<endl;
}
}
E：Evil Coordinate
??賽中把這道題考慮成一道分情況討論的題目了…如果真的要分類討論，并且要給出一種可行的構造方案（不通過給出序列然后驗證的方式），會需要非常大的思維量，賽中AC代碼：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46179825
??看了題解明白其實還有一種做法，就是暴力列舉，但是我們不會暴力列舉所有的排列組合，而只是列舉U，D，L，R四種方式的排列即可（一走就走完，這種做法肯定沒有問題），
#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
string goal="UDLR";
int num[4];
string Construct(int a,int b,int c,int d)
{
string ans="";
for(int i=0;i<num[a];++i) ans+=goal[a];
for(int i=0;i<num[b];++i) ans+=goal[b];
for(int i=0;i<num[c];++i) ans+=goal[c];
for(int i=0;i<num[d];++i) ans+=goal[d];
return ans;
}
bool Check(int x,int y,string ans)
{
int curx=0,cury=0;
if(x==0 && y==0) return false;
int len=ans.length();
for(int i=0;i<len;++i)
{
if(ans[i]=='U') cury++;
else if(ans[i]=='D') cury--;
else if(ans[i]=='L') curx--;
else curx++;
if(curx==x && cury==y) return false;
}
cout<<ans<<endl;
return true;
}
bool solve(int x,int y,string s)
{
int len=s.length();
for(int i=0;i<4;++i) num[i]=0;
for(int i=0;i<len;++i)
{
if(s[i]=='U') num[0]++;
else if(s[i]=='D') num[1]++;
else if(s[i]=='L') num[2]++;
else num[3]++;
}
for(int i=0;i<4;++i)
for(int j=0;j<4;++j)
for(int k=0;k<4;++k)
for(int l=0;l<4;++l)
{
if(i==j || i==k || i==l || j==k || j==l || k==l) continue;
string ans=Construct(i,j,k,l);
if(Check(x,y,ans)) return true;
}
return false;
}
int main()
{
close;
int T;cin>>T;
while(T--)
{
int x,y;cin>>x>>y;
string s;cin>>s;
if(!solve(x,y,s)) cout<<"Impossible"<<endl;
}
}
F：Fireworks
??我們令
q
=
1
?
p
/
10000.0
q=1-p/10000.0
q=1?p/10000.0，那么成功的概率就是
1
?
q
x
1-q^x
1?qx，那么如果我們在第一次制作
x
x
x個煙花失敗了，我們會回到初始狀態，這個時候我們會再次選擇做
x
x
x個煙花（因為我們認為
x
x
x是這里的最優解，那么我們失敗的時候肯定會選擇最優解繼續做下去），那么如果找到這個最優解，其實就是求解
f
(
x
)
=
x
?
n
+
m
1
?
q
x
f(x)=\frac {x*n+m}{1-q^x}
f(x)=1?qxx?n+m?，我們想要計算
x
x
x是整數時的最小值，
f
(
x
)
=
x
?
n
+
m
1
?
q
x
f(x)=\frac {x*n+m}{1-q^x}
f(x)=1?qxx?n+m?
∴
f
′
(
x
)
=
n
(
1
?
q
x
)
?
(
n
x
+
m
)
(
?
q
x
?
ln
?
q
)
(
1
?
q
x
)
2
\therefore f'(x)=\frac {n(1-q^x )-(nx+m)(-q ^x\cdot\ln{q})}{(1-q ^x) ^2}
∴f′(x)=(1?qx)2n(1?qx)?(nx+m)(?qx?lnq)?
令
T
(
x
)
=
n
(
1
?
q
x
)
?
(
n
x
+
m
)
(
?
q
x
?
ln
?
q
)
，
則
有
：
令T(x)=n(1-q^x )-(nx+m)(-q ^x\cdot\ln{q})，則有：
令T(x)=n(1?qx)?(nx+m)(?qx?lnq)，則有：
T
′
(
x
)
=
(
n
?
ln
?
2
q
?
x
+
m
?
ln
?
2
q
)
?
q
x
>
0
恒
成
立
(
x
>
0
)
T'(x)=(n\cdot{\ln ^2 q}\cdot x+m\cdot{\ln ^2 q})\cdot q ^x>0恒成立(x>0)
T′(x)=(n?ln2q?x+m?ln2q)?qx>0恒成立(x>0)因此，我們可以得出
T
(
x
)
T(x)
T(x)單調遞增，又由于
lim
?
n
→
0
T
(
x
)
<
0
\lim_{n \to 0} T(x)<0
limn→0?T(x)<0，因此
f
(
x
)
f(x)
f(x)是個單峰函式（先減后增），
??在明確了
f
(
x
)
f(x)
f(x)是個單峰函式以后，我們就可以使用三分法，注意不同的三分判斷條件可能導致答案離正確答案還有些許的距離（誤差），要在一個小范圍內找到正確的答案！
#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
double n,m,p,q;
const double eps=1e-6;
inline double poww(double base,ll x)
{
double ans=1.0;
while(x){if(x&1) ans=ans*base;base=base*base;x>>=1;}
return ans;
}
double cal(ll x) {return (n*x+m)/(1.0-poww(q,x));}
int main()
{
close;int T;cin>>T;
while(T--)
{
cin>>n>>m>>p;
q=1-p/10000.0;
ll l=1,r=1e13+100;
while(l<r)
{
ll mid=(l+r)/2,midd=(mid+r)/2;
double ans1=cal(mid),ans2=cal(midd);
if(ans1-ans2>=eps) l=mid;
else r=midd;
}
double res=LONG_LONG_MAX;
ll lbound=max(l-5,1ll),rbound=l+5;
for(int i=lbound;i<=rbound;++i)
res=min(res,cal(i));
printf("%.10f\n",res);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/238625.html
標籤：其他