比賽鏈接
https://ac.nowcoder.com/acm/contest/13926
F.Group Project
首先肯定可以劃分成兩個班級的，且班級內不會有沖突，那么肯定優先選擇班級內配對，最后如果每個班都剩一個，且此時 cnta*cntb!=m，那么這兩個人能配對，答案+1(cnta，cntb代表每個班級的人數，如果相乘不等于m，那么肯定存在當前班級的一個人可以和另一個班級的一個人配對)，然后用并查集實作即可，
這里把for回圈換成while(m–)就過不了，
# include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int fa[N];
int enemy[N];
int find_fa(int x)
{
if(x==fa[x])
return x;
else
return fa[x]=find_fa(fa[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
fa[i]=i;
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
if(enemy[x])
{
if(find_fa(enemy[x])!=find_fa(y))
fa[fa[y]]=fa[enemy[x]];
}
else
enemy[x]=y;
if(enemy[y])
{
if(find_fa(enemy[y])!=find_fa(x))
fa[fa[x]]=fa[enemy[y]];
}
else
enemy[y]=x;
}
int root=find_fa(1);
int cnta=0;
int cntb=0;
for(int i=1;i<=n;++i)
{
if(fa[i]==root)
cnta++;
else
cntb++;
}
if(cnta%2==1&&cntb%2==1&&cnta*cntb!=m)
printf("%d\n",cnta/2+cntb/2+1);
else
printf("%d\n",cnta/2+cntb/2);
}
G.Human Pyramid
思維+dp，strong的要不站在最底下，要不下面要有兩個strong支撐，
我們換個方向看(按斜線方向看)，strong要不是連續的，要不就是單獨在最下面，所以我們可以按斜線方向進行dp，dp[i][j][k]表示第i行至少有連續
k個strong，且前i行有j個strong的方案數，（這里的行數是看斜線方向）
狀態轉移方程如下：
dp[i][j][k]=dp[i-1][j-k][max(0,k-1)]+dp[i][j][k+1]
解釋如下：
如果 i 行用k個strong，那么可由前一行 i-1行 轉移到，那么前 i-1 行肯定是用 j-k個strong且第 i 行至少用 k-1個strong，(當然k=0時，前面也得至少用0個，所以和0取個max)
如果 i 行用大于 k 個strong，那么可由至少用 k+1 個strong轉移到，
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll dp[105][5305][105]; //dp[i][j][k]表示第i行至少選k個strong,且一共選j個strong的方案數
int main()
{
int h,s;
cin>>h>>s;
dp[0][0][0]=1;
for(int i=1;i<=h;++i)
for(int j=0;j<=s;++j)
for(int k=min(i,j);k>=0;k--)
dp[i][j][k]=(dp[i][j][k+1]+dp[i-1][j-k][max(0,k-1)])%mod;
cout<<dp[h][s][0]<<endl;
return 0;
}
H.In-place Sorting
貪心的想法，如果當前第i個數ai已經大于等于前面的了，要讓他盡可能小，這樣后面才能更容易滿足條件，每次先把6全部改成9，看此時是否大于等于前面，如果不滿足輸出impossible，否則從高位向后依次，把9改為6，看是否滿足，如果不滿足改回9，如果滿足繼續向后重復此操作，因為如果當前能把9改為6，那么之后肯定不會出現情況，讓前面的6重新改回9，
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n;
string a[N];
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=0;a[1][i];++i)
{
if(a[1][i]=='9')
a[1][i]='6';
}
for(int i=2;i<=n;++i)
{
if(a[i].size()<a[i-1].size())
{
puts("impossible");
return 0;
}
if(a[i].size()>a[i-1].size())
{
for(int j=0;a[i][j];++j)
if(a[i][j]=='9')
a[i][j]='6';
continue;
}
for(int j=0;a[i][j];++j)
if(a[i][j]=='6')
a[i][j]='9';
if(a[i]<a[i-1])
{
puts("impossible");
return 0;
}
for(int j=0;a[i][j];++j)
{
if(a[i][j]=='9')
a[i][j]='6';
if(a[i]>=a[i-1])
continue;
a[i][j]='9';
}
}
puts("possible");
for(int i=1;i<=n;++i)
cout<<a[i]<<endl;
return 0;
}
I.Jam-packed
很簡單的二分，首先想到最小數量具有單調性（因為如果當前情況滿足的話，比當前情況小的肯定也滿足check條件），因為箱子是無限個，所以最小數量多小都可以，所以 l=1，而最大數量也不可能超過上限 r=k，然后對于每個mid, 判斷是否滿足條件(先按每箱放mid個，那么最后會剩n%mid個，所以要將最后的n%mid個放到前面n/mid個箱子上，即判斷 n%mid是否小于等于 (k-mid)*(n/mid)，如果滿足就可以，不滿足就不可以）PS:或者直接公式 n/(n/k + 1)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
inline __int128 read(){
__int128 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 * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void print(__int128 x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
__int128 n,k;
bool check(__int128 x)
{
if(n%x==0)
return 1;
__int128 res=n%x;
__int128 num=n/x;
return res<=num*(k-x);
}
int main()
{
n=read();
k=read();
__int128 l=1;
__int128 r=k;
__int128 mid;
__int128 ans=0;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
ans=max(ans,mid);
l=mid+1;
}
else
r=mid-1;
}
print(ans);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275546.html
標籤：其他