1842A - Tenzing and Tsondu
題意
丁真和珍珠寶可夢(mèng)對(duì)決, 每個(gè)寶可夢(mèng)都有x戰(zhàn)力, 假設(shè)有兩個(gè)寶可夢(mèng), 其戰(zhàn)力分別為a和b(a>b), 戰(zhàn)力為a的寶可夢(mèng)獲勝后戰(zhàn)力-b, 而戰(zhàn)敗的寶可夢(mèng)會(huì)消失
最后還有寶可夢(mèng)的人獲勝
問(wèn)你丁真和珍珠誰(shuí)贏了
題解
顯而易見(jiàn), 贏下來(lái)的寶可夢(mèng)可以繼續(xù)打, 輸了的就會(huì)消失, 所以是比戰(zhàn)力值總和
代碼
void solve()
{
cin>>n>>m;
vector<ll>a(n+1);
ll u,v;
u=v=0;
rep(i,1,n) cin>>a[i],u+=a[i];
vector<ll>b(m+1);
rep(i,1,m) cin>>b[i],v+=b[i];
if(u==v) cout<<"Draw"<<endl;
else if(u>v)cout<<"Tsondu"<<endl;
else cout<<"Tenzing"<<endl;
return;
}
1842B - Tenzing and Books
題意
丁真收到了三堆書(shū), 每堆書(shū)有
n
n
n本, 每本書(shū)有固定的知識(shí)值
a
[
i
]
a[i]
a[i]
每讀一本書(shū)就會(huì)使得丁真的知識(shí)值與這本書(shū)的知識(shí)值進(jìn)行或運(yùn)算
即
a
n
s
∣
=
a
[
i
]
ans|=a[i]
ans∣=a[i]
丁真會(huì)從書(shū)堆的開(kāi)頭第一本開(kāi)始讀
每當(dāng)丁真不想讀下去時(shí), 他會(huì)直接放棄一整堆書(shū)
丁真想讓他的知識(shí)值達(dá)到ans, 問(wèn)你這可能嗎
題解
因?yàn)槭腔蜻\(yùn)算, 思路直接來(lái)到了位運(yùn)算
首先, 假設(shè)ans的二進(jìn)制是10011
那么想要讓丁真達(dá)到ans這個(gè)值, 我們需要注意一些點(diǎn)
因?yàn)槭腔蜻\(yùn)算, 書(shū)的知識(shí)值中二進(jìn)制為0是不會(huì)對(duì)答案造成影響的
若同一個(gè)二進(jìn)制位中, 書(shū)的知識(shí)值為1而答案為0, 那么就對(duì)答案造成了偏差
那么以貪心的思想, 只要不會(huì)對(duì)答案造成影響的(即 b o o k > > i & 1 book>>i\&1 book>>i&1==1&&ans>>i&1!=0), 丁真都可以讀
那么答案顯而易見(jiàn), 對(duì)所有能讀的書(shū)都給讀了, 遇到不能讀的書(shū)就退出書(shū)堆, 最后對(duì)比答案就可以了
代碼
void solve()
{
cin>>n>>m;
vector<ll> a(n+1);
ans=0;
rep(i,1,n) cin>>a[i];
rep(i,1,n)//這段for重復(fù)三遍
{
ll mk=0;
for(ll j=0;j<=32;j++)
{
cnt=(m>>j)&1;
ant=(a[i]>>j)&1;
if((ant&&cnt==0))
{
mk=1;
break;
}
}
if(mk) break;
ans|=a[i];
}
rep(i,1,n) cin>>a[i];
rep(i,1,n)
{
ll mk=0;
for(ll j=0;j<=32;j++)
{
cnt=(m>>j)&1;
ant=(a[i]>>j)&1;
if(ant&&cnt==0)
{
mk=1;
break;
}
}
if(mk) break;
ans|=a[i];
}
rep(i,1,n) cin>>a[i];
rep(i,1,n)
{
ll mk=0;
for(ll j=0;j<=32;j++)
{
cnt=(m>>j)&1;
ant=(a[i]>>j)&1;
if(ant&&cnt==0)
{
mk=1;
break;
}
}
if(mk) break;
ans|=a[i];
}
if(ans==m) yes
else no
return;
}
解法2
源代碼出自
用&的方式省去了位運(yùn)算枚舉
很妙
1842C - Tenzing and Balls
題意
n個(gè)球排成一列, 每個(gè)球都有一個(gè)特定的顏色值
丁真可以選擇兩個(gè)顏色值一樣的球, 刪除這這兩個(gè)球之間的所有球(包括這兩個(gè)球)這個(gè)操作可以進(jìn)行無(wú)限次
問(wèn)你最多能刪多少個(gè)球
題解
這題一開(kāi)始以為是雙指針假了, 其實(shí)是dp
使用兩個(gè)數(shù)組進(jìn)行動(dòng)態(tài)規(guī)劃
d數(shù)組用于存儲(chǔ)這個(gè)元素的最優(yōu)解, 而f數(shù)組用于存儲(chǔ)當(dāng)前下標(biāo)的最優(yōu)解(即答案)
則動(dòng)態(tài)轉(zhuǎn)移方程(設(shè)當(dāng)前元素為x)
f[i]=min(f[i-1]+1,d[x]);//選擇該元素的最優(yōu)解(若沒(méi)出現(xiàn)過(guò)則為INF), 或者不選(答案+1)
d[x]=min(f[i-1],d[x]);//該元素的最優(yōu)解=當(dāng)前局部最優(yōu)解和元素最優(yōu)解取min
最后答案為n-f[n]
代碼
void solve()
{
cin>>n;
vector<ll>a(n+1),f(a),d(n+1,INF);
rep(i,1,n)
cin>>a[i];
rep(i,1,n)
{
ll x=a[i];
f[i]=min(f[i-1]+1,d[x]);
d[x]=min(f[i-1],d[x]);
}
cout<<n-f[n]<<endl;
return;
}
1842D - Tenzing and His Animal Friends
題意
這題題面很抽象, 我看了至少半小時(shí)才看懂(也可能是因?yàn)橛⒄Z(yǔ)太菜了, 嗯造機(jī)翻)
最后看了公告才看懂的
丁真和他的n個(gè)動(dòng)物朋友玩耍, 丁真非常喜歡他的1號(hào)朋友, 所以每次都要和1號(hào)朋友玩, 丁真不喜歡他的n號(hào)朋友, 所以丁真不和n號(hào)朋友玩
現(xiàn)在給出m個(gè)限制, 每個(gè)限制有u v w三個(gè)參數(shù), 代表u號(hào)朋友和v號(hào)朋友不在一起的時(shí)間不超過(guò)w
(u和v同時(shí)都在和同時(shí)不在的時(shí)間不會(huì)被此條限制所影響)
丁真想盡可能用更多的時(shí)間和動(dòng)物朋友們玩耍
請(qǐng)輸出丁真最多能和動(dòng)物朋友玩耍的時(shí)間和玩耍的次數(shù)
用二進(jìn)制狀態(tài)表示丁真和哪些動(dòng)物朋友們玩耍, 并在同一行那一次輸出玩耍了多久
題解
首先1和n一定要在一個(gè)連通塊中, 不一定需要1和n在一條邊上但一定要在一個(gè)連通塊中, 若1和n不在一個(gè)連通塊中, 我們就可以一直構(gòu)造11111…11110這樣的玩法持續(xù)無(wú)限次, 因?yàn)?和n并不相連, 所以不存在只允許出1而不出現(xiàn)n的次數(shù)限制 (注意題目條件n不能出現(xiàn), 1必須出現(xiàn)) , 因此可以一直構(gòu)造這樣的玩法
相應(yīng)的, 從1到n的最短路, 也就是此題中丁真最多能和動(dòng)物朋友有玩的時(shí)間了
(這題的難度就在這里了, 當(dāng)時(shí)想破了腦袋也沒(méi)想出這題是個(gè)最短路)
然后將數(shù)據(jù)分為兩類(lèi), 一類(lèi)是可以和1一起玩的, 另一類(lèi)是不能和1一起玩的
按照貪心的思想, 每次都將能和1一起有玩的所有動(dòng)物朋友都加進(jìn)去, 而游玩時(shí)間就是其中能和1玩的動(dòng)物朋友中, 能玩時(shí)間的最小值 (也就是他到n的最短路/或者1到n的最短路 這里取最小值 再減去上一個(gè)次游玩的時(shí)間, 原因是有上一次游玩時(shí)間和這一次游玩時(shí)間有交集部分 而交集部分正好是上一次游玩的時(shí)間)
按照這樣下去, 每次游玩都必定淘汰至少一個(gè)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-527346.html
代碼
void solve()
{
cin>>n>>m;
rep(i,1,n)
rep(j,1,n)
{
if(i!=j) cnt=llINF;
else cnt=0;
a[i][j]=cnt;
}
rep(i,1,m)
{
ll u,v,w;
cin>>u>>v>>w;
a[u][v]=a[v][u]=w;
}
rep(k,1,n)
rep(i,1,n)
rep(j,1,n)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
if(a[1][n]==llINF)
{
cout<<"inf"<<endl;
return;
}
vector<ll>d(n+1),dist;
cnt=a[1][n];
rep(i,1,n)
{
d[i]=min(cnt,a[i][n]);
dist.push_back(d[i]);
}
sort(dist.begin(),dist.end());
dist.erase(unique(dist.begin(),dist.end()),dist.end());
cout<<cnt<<' '<<dist.size()-1<<endl;
cnt=0;
repr(i,0,dist.size())
{
if(!dist[i]) continue;
rep(j,1,n) cout<<(d[j]>=dist[i]);
cout<<' '<<dist[i]-cnt<<endl;
cnt=dist[i];
}
return;
}
這里用的Floyd求最短路, 當(dāng)然你用dijkstra也是可以的文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-527346.html
到了這里，關(guān)于CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) A-D的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
