本场比赛之所以会被我打，是因为在前几天晚上，我发现它的难度是$Div.4$；而过了几天后，它的难度变成了Div.3。

所以，可以推出，它的难度在Div.4与Div.3之间，CF官方纠结了半天最终把难度改为了Div.3；因此，这场比赛的难度会比Div.3的难度小一些。

于是就开始打了~
(手动滑稽)

A

Solution

设长方形的长和宽分别为$a$和$b$，不妨设$a>b$。

①把宽边乘2作为正方形的一边，必须有$2a\ge b$。此时面积为 ( 2 a ) 2 (2a)^2 (2a)2。

②宽边乘2不可作为正方形的一边，必须有$2a＜b$。此时面积为 b 2 b^2 b2。

按照上述方法$O(t)$模拟即可。

Code

#include 
#define int long long
using namespace std;int t,n,m;signed main()
{cin>>t;while (t--){cin>>n>>m;if (n>m)  swap(n,m);if (2*n>=m)  cout<<(2*n)*(2*n)<<endl;else cout<<m*m<<endl; }return 0;
}

B

Solution

排序后，贪心寻找一个$i$，使得 a i − a i − 1 a_i-a_{i-1} ai​−ai−1​的值最小。显然此时枚举$i$即可。

时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)。

#include 
#define int long long
using namespace std;int t,n;
int a[200005];signed main()
{cin>>t;while (t--){cin>>n;for (int i=1;i<=n;i++)  cin>>a[i];sort(a+1,a+n+1);int ans=1e9+7;for (int i=1;i<=n-1;i++)  ans=min(ans,a[i+1]-a[i]);cout<<ans<<endl;}return 0;
}

C

Solution

显然，我们贪心地先用桶来判断，能否通过同奇偶配对来用掉所有的数。

如果可以，那么显然输出$Yes$。否则，由于$n$为偶数，必然会留下两个数(一奇一偶)。

此时，再回到原数列中寻找两个数$x$与$y$，使得它们的差为$1$(且它们一奇一偶)。如果找到了，那么我们就能规划出这样的方案：除$x$与$y$之外的数两两同奇偶配对，最后$x$与$y$配对。如果没找到就输出NO。

Code

#include 
#define int long long
using namespace std;int t,n;
int a[105];signed main()
{cin>>t;while (t--){	cin>>n;for (int i=1;i<=n;i++)  cin>>a[i];int b[5]={0};for (int i=1;i<=n;i++)  b[a[i]%2]++;b[0]%=2,b[1]%=2;if (b[0]==0&&b[1]==0){cout<<"YES"<<endl;continue;}int flag=0;for (int i=1;i<=n-1;i++){for (int j=i+1;j<=n;j++){if (a[i]+1==a[j]||a[j]+1==a[i]){flag=1;break;}}if (flag==1)  break;}if (flag==1)  cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}

D

Solution

把题目简化一下，就是要求出最小的$i$使得$i|n$且$i\le k$，答案就是 n i \frac n i in​。

注意枚举约数只需要枚举到 n \sqrt n n ​。如果枚举到了$j$使得$j|n$，那么 n j \frac n j jn​就是另外一个约数。

故时间复杂度为 O ( t n ) O(t \sqrt n) O(tn ​)。

Code

#include 
#define int long long
using namespace std;int t,n,k;signed main()
{cin>>t;while (t--){cin>>n>>k;int minv=1e9+7;for (int i=1;i*i<=n;i++){if (n%i==0){if ((n/i)<=k)  minv=min(minv,i);if (i<=k)  minv=min(minv,n/i);}}cout<<minv<<endl;}return 0;
}

E

Solution

题面较长，但是事实上十分简单。

如果存在位置 a i , j a_{i,j} ai,j​为$1$，那么它的下方的格子，和右方的格子必须至少有一个位$1$，否则就宣告该盘面不存在。

时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

Code

#include 
#define int long long
using namespace std;int t,n;
int a[55][55],dp[55][55];signed main()
{cin>>t;while (t--){cin>>n;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){char x;cin>>x;a[i][j]=x-'0';dp[i][j]=0;}}for (int i=0;i<=n+1;i++){for (int j=0;j<=n+1;j++){if (i==0||i==n+1||j==0||j==n+1)  a[i][j]=1;}}int flag=1;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (a[i][j]==0)  continue;if (a[i+1][j]==0&&a[i][j+1]==0){flag=0;break;}}}if (flag==1)  cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
} 

F

Solution

①如果第一个字符串满足要求，那么就输出它；

②如果第一个字符串不满足要求，那么我们枚举它的某一位并枚举将该位修改成什么，然后再看看修改后的字符串是否满足要求。若满足要求，就输出它。

如果通过①②均找不到答案，那么显然输出$-1$。

时间复杂度 O ( n m 2 ) O(nm^2) O(nm2)。

Code

#include 
#define int long long
using namespace std;int t,n,m;
char a[15][15];signed main()
{cin>>t;while (t--){cin>>n>>m;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++)  cin>>a[i][j];}int done=0,flag=1;for (int i=2;i<=n;i++){int dog=0;for (int j=1;j<=m;j++){if (a[i][j]!=a[1][j])  dog++;}if (dog>1){flag=0;break;}}if (flag==1){for (int i=1;i<=m;i++)  cout<<a[1][i];cout<<endl;continue;}for (int i=1;i<=m;i++){for (char j=0;j<=25;j++){char save=a[1][i];a[1][i]=j+'a';int flag=1;for (int k=2;k<=n;k++){int dog=0;for (int w=1;w<=m;w++){if (a[k][w]!=a[1][w])  dog++;}if (dog>1){flag=0;break;}}if (flag==1){for (int k=1;k<=m;k++)  cout<<a[1][k];cout<<endl;done=1;break;}a[1][i]=save;}if (done==1)  break;}if (done==0)  cout<<-1<<endl;}return 0;
}

G

咕个屁

Solution

对于每行，我们均贪心地先在这样的格子填$1$: 该格子所在的列中，所需要另填的$1$的数量最多。

最终判断一下矩阵是否满足要求即可。

时间复杂度: $O(tnm)$。

Code

#include 
#define int long long
using namespace std;int t,n,m,a,b;
int ans[105][105],h[105];struct node
{int rt;int num;
}l[105];bool cmp(node a,node b)
{return a.num>b.num;
}signed main()
{cin>>t;while (t--){memset(ans,0,sizeof(ans));memset(h,0,sizeof(h));cin>>n>>m>>a>>b;for (int i=1;i<=m;i++){l[i].rt=i;l[i].num=b;}for (int i=1;i<=n;i++)  h[i]=a;for (int i=1;i<=n;i++){sort(l+1,l+m+1,cmp);for (int j=1;j<=h[i];j++){ans[i][l[j].rt]=1;l[j].num--;}}int flag=1;for (int j=1;j<=m;j++){int tot=0;for (int i=1;i<=n;i++){if (ans[i][j]==1)  tot++;}if (tot!=b){flag=0;break;}}if (flag==1){cout<<"YES"<<endl;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++)  cout<<ans[i][j];cout<<endl;}}else cout<<"NO"<<endl;}return 0;
}

H

Solution

做完就疯掉了

首先，我们定义本题中排名的概念：将该$n$个数去掉后，剩下的数按升序排列，$i$的排名就是此时小于等于i的数的数量。如样例中的第一组测试中，$000$的排名为$1$，$100$的排名为$3$。同时定义所求答案的排名为$rank$。

然后，发现排名是有单调性的。即若$i＜j$，那么必然有$i$的排名在$j$的排名之前。于是，我们可以二分查找这样的$i$使得$i$的排名为$rank$。

现在难点在于如何快读求得$i$的排名。显然，$i$的排名就是$(i+1)$减去比它小的数的个数。那么如何快速求比它小的数的个数呢？显然，可以先将那需要删除的$m$个数按升序排列，查询的时候再次使用二分即可快速求出。

综上所述，时间复杂度为 O ( m l o g 2 n ) O(mlog_2n) O(mlog2​n)。

编代码时出现了许多问题，这里跟大家说一下。

① 如何二分？
读入进来的都是二进制数，我们把它们统统转换为十进制数，然后正常地二分；输出的时候转成二进制即可。

② 用位运算$(1<<m)$怎么出现了溢出的问题？
开$long$ $long$，把位运算转换成以2为底的快速幂即可。

③ 如何控制当前二分的$mid$不是被删掉的数？
不用控制。此时的$mid$是满足排名的条件的，我们在二分之后只需要不停地将答案减一，直到当前答案不会被删。此时显然排名仍然满足要求。

④ 根据③的说法，怎么快速判断这个数是否会被删掉呢？

直接用$map$记录即可。

Code

#include 
#define int long long
using namespace std;int t,n,m,ans,Rank,pos=0;
int a[200005];map<int,int> ma;int quick_power(int x,int y)
{int res=1;for (;y;y=y>>1,x=(x*x)){if (y&1)  res=res*x;}return res;
}inline int check(int x)
{int cnt=x+1-(upper_bound(a+1,a+n+1,x)-a-1);return cnt;
}inline void Binary_search(int l,int r)
{if (l==r||l+1==r){if (check(l)==Rank)  ans=l;else if (check(r)==Rank)  ans=r;return;}int mid=(l+r)>>1,value=check(mid);if (value<Rank)  Binary_search(mid,r);else if (value==Rank){ans=mid;return;}else Binary_search(l,mid);
}signed main()
{cin>>t;while (t--){ma.clear(),pos=0;cin>>n>>m;for (int i=1;i<=n;i++){string s;cin>>s;int tot=0,pos=1;for (int j=s.size()-1;j>=0;j--){tot=tot+(s[j]-'0')*pos;pos*=2;}a[i]=tot;ma[tot]=1;}sort(a+1,a+n+1);Rank=quick_power(2,m)-n;if (Rank%2==1)  Rank=(Rank+1)/2;else Rank/=2;Binary_search(1,quick_power(2,m));while (ma[ans]==1)  ans--;int p[105]={0};while (ans!=0){p[++pos]=ans%2;ans/=2;}for (int i=m;i>=1;i--)  cout<<p[i];cout<<endl;}return 0;
}

撒花✿✿ヽ(°▽°)ノ✿撒花

总结

只想说两个字:

耍巧

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！