Educational Codeforces Round 80 (Rated for Div. 2) - Codeforces
Problem - A - Codeforces
数学
双钩函数，直接显然极值点是\(\sqrt{d}-1\),但要注意取整的时候可能存在偏差，暴力搜索一下附近的值就好了
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,d;scanf("%d%d",&n,&d);
if(n>=d){cout<<"YES"<<endl;return ;}
int x=pow(d*1.0,0.5);
for(int i=-2;i<=2;i++)
{
int u=i+x;
if(u>=1&&u<=n)
{
int f=u+(d+u)/(u+1);//向上取整
if(n>=f)
{
cout<<"YES"<<endl;
return ;
}
}
}
cout<<"NO"<<endl;
}
int main()
{
int t;cin>>t;
while(t--)solve();
}
Problem - B - Codeforces
构造
设\(y\)为\(b\)的位数
\[a*b+a+b=conc(a,b)=a*10^{y}+b\\ a*b+a=a*(b+1)=a*10^{y}\\ b+1=10^{y} \]显然\(a\)可以取任意值，\(b\)只能取\(9,99,999.....\)
#include<bits/stdc++.h>
using namespace std;
int n,m;
void solve()
{
int a,b;scanf("%d%d",&a,&b);
int cnt=9;long long ans=0;
while(cnt<=b)
{
ans++;
cnt=cnt*10+9;
}
cout<<ans*a<<endl;
}
int main()
{
int t;cin>>t;
while(t--)solve();
}
Problem - C - Codeforces
\(DP\) 排序
观察题目我们可以发现两个数组可以直接拼起来（分开来做也差不多）
\(a_1\leq a_2...\leq a_m\leq b_m ..\leq b_2\leq b_1\)
题目就变成了求满足最大值不超过\(n\)的，长度为\(2*m\)的不递减序列的个数(对他使用\(dp\)吧！)
定义\(dp[i][j]\)为长度为\(i\)，末尾元素为\(j\)的序列的个数
观察前后项的递推关系发现，在\(i-1\)中的每个小于\(j\)的序列后面都可以接上一个\(j\).
那么转移方程就很显然了\(dp[i][j]=\sum_{k=1}^{j}dp[i-1][k]\)
关注一下\(dp\)的初始化问题,先写出代码，从\(i=2\)开始遍历，我们发现第一次求解的时候利用的是\(dp[1][k]\)的值
只需将\(1:n\)的\(dp[1][i]\)初始化即可
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e9+7;
int n,m;
int dp[N][N];
long long ans;
int main()
{
scanf("%d%d",&n,&m);
m=m*2;
for(int i=1;i<=n;i++)dp[1][i]=1;
for(int i=2;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=j;k++)
{
dp[i][j]=(0LL+dp[i][j]+dp[i-1][k])%M;
}
}
}
for(int i=1;i<=n;i++)ans=(ans+dp[m][i])%M;
cout<<ans<<endl;
}
Problem - D - Codeforces
状态压缩 二分
说实话看到最大的最小值就该想到二分的，但我不会状压....
给出一个 \(n\) 行 \(m\) 列的数字矩阵 \(a\)，找出两行 \(x, y\)，令 \(b_j = \max(a_{x, j}, a_{y, j})\)，试使得 \(\min\limits_{1 \le j \le m}b_j\) 最大，输出选择的 \(x, y\)，可以相同。
我们先看看数据范围\(n\leq 3e5,b\leq 8\),感觉奇奇怪怪
基本思路是先二分出答案要求的\(\min\limits_{1 \le j \le m}b_j\)，然后根据这个值找到对应的\(x,y\)
关键在于\(check\)函数和查找，\(n\)的范围很大，暴力显然会超时，这里可以用二进制压缩
在二分的时候，把每个\(\geq mid\)的数字设置为\(1\)，反之设置为\(0\)，然后将这行数字看作一个二进制数
如果有两行数组符合条件，显然他们的按位或的结果为\(11...11=2^m-1\)(或者单独一行为\(2^m-1\)也行)
由于\(m=8\),暴力枚举\(2^m*2^m=2^{2*m}=65536\)，可以接受，直接设置一个\(cnt\)数组来记录即可
时间复杂度：\(log(le9)*(n*m+2^{2*m})\)
然后就是一些关于位运算的东西，要注意\((1<<m)\)这种东西最好加个括号....
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int a[N][10];
int cnt[1<<9];
int n,m;
bool check(int x)
{
memset(cnt,0,sizeof cnt);
for(int i=1;i<=n;i++)
{
int res=0;
for(int j=1;j<=m;j++)
{
res=res*2+(a[i][j]>=x);
}
cnt[res]=i;
}
for(int i=0;i<=(1<<m)-1;i++)
{
for(int j=0;j<=(1<<m)-1;j++)
{
if(cnt[i]&&cnt[j]&&(i|j)==(1<<m)-1)return true;
}
}
return false;
}
void ans(int x)
{
memset(cnt,0,sizeof cnt);map<int,int>mp;
for(int i=1;i<=n;i++)
{
int res=0;
for(int j=1;j<=m;j++)
{
res=res*2+(a[i][j]>=x);
}
cnt[res]=i;
}
for(int i=0;i<=(1<<m)-1;i++)
{
for(int j=0;j<=(1<<m)-1;j++)
{
if(cnt[i]&&cnt[j]&&(i|j)==(1<<m)-1)
{
cout<<cnt[i]<<' '<<cnt[j]<<endl;return ;
}
}
}
}
void solve()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
int l=0,r=1e9+10;
while(l<r)
{
int mid=(l+1+r)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
ans(l);
}
int main()
{
int t=1;
while(t--)solve();
}