与博客园 cf1530-CodeforcesRound733（div1+div2）A~D - Alex_Chao - 博客园为同一作者。
题意：
定义：只包含0和1的十进制数称为（Binary Decimal），给定一个正整数N，求以最少的分解数量将其分解为Binary Decimal的分解数是多少。
思路：
分析样例，其实就是找各数位中最大的数，比如121->2，789->9
代码：
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> vint;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
const int mod = 1e9+7;
ll qpow(ll a,ll b){ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;}
template<typename T>
inline void read( T&x )
{
int f=1;x=0;char c=getchar();
while(c>'9'||c<'0')
{
if(c=='-') f=-1;c=getchar();//ÅжÏÊÇ·ñΪ¸º
}
while(c>='0'&&c<='9') x=10*x+c-48,c=getchar();
x=x*f;
}
int t;
string s;
int main(){
read(t);
while(t--){
cin>>s;
char minx='0';
for(char c:s){
minx=max(minx,c);
}
cout<<minx<<endl;
}
return 0;
}
题意：
给出n和m，求一个n*m的01矩阵，要求只有四条边有1，中间全是0，且每个1附近八个方向的八个点都是0
思路：
贪心
代码：
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> vint;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
const int mod = 1e9+7;
ll qpow(ll a,ll b){ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;}
template<typename T>
inline void read( T&x )
{
int f=1;x=0;char c=getchar();
while(c>'9'||c<'0')
{
if(c=='-') f=-1;c=getchar();//ÅжÏÊÇ·ñΪ¸º
}
while(c>='0'&&c<='9') x=10*x+c-48,c=getchar();
x=x*f;
}
int t,n,m;
int matrix[50][50];
int main(){
read(t);
while(t--){
memset(matrix,0,sizeof(matrix));
read(n);read(m);
int i;
for(i=1;i<=m;i+=2) matrix[1][i]=1;
for(i=3;i<=n;i+=2) matrix[i][1]=matrix[i][m]=1;
for(int j=3;j<=m-2;j+=2) matrix[n][j]=1;
for(i=1;i<=n;++i) {
for(int j=1;j<=m;++j) cout<<matrix[i][j];
cout<<endl;
}
}
return 0;
}题意：
给出A，B两个长度为N的数组，定义数组的有效得分为最大的前（L-L/4）个分数之和，其中L为数组长度。求这两个数组需要增加同时多少个元素，才能是的A的得分大于B
补充条件：数组中的每个元素Ai∈[0, 100]
思路：
观察样例，最优解是A每次增加值为100的元素，B每次增加值为0的元素。
先将B的结果预处理出来，因为B每次都增加0，所以被算入总分的部分不会有变动，只会有慢慢扩张到最后停滞。详见代码第41~42行
预处理A在数组长度为 k 时候的结果，需要将增加了x个元素直接算入总和当中，在添加A数组当中的（k-k/4-x）的前缀和。详见代码第40行与第24~27行。
根据算出来的A和B，二分需要增加的场数x。
代码：
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> vint;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
const int mod = 1e9+7;
ll qpow(ll a,ll b){ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;}
const int N=4e5+5;
int t,n,a[N],b[N];
ll sa[N],sb[N];
inline bool cmp(int a,int b){
return a>b;
}
inline bool check(int x){
int ssa=x*100;
int y=x+n;
int tmp=y-y/4;
ssa+=sa[tmp-x];
return ssa<sb[tmp];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
cin>>n;
sa[0]=sa[1]=sb[0]=sb[1]=0;
rep(i,1,n+1) cin>>a[i];
rep(i,1,n+1) cin>>b[i];
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
rep(i,1,n+1) sa[i]=sa[i-1]+a[i];
rep(i,1,n+1) sb[i]=sb[i-1]+b[i];
rep(i,n+1,2*n+1) sb[i]=sb[i-1];
//cout<<"\nsahesb\n";
//rep(i,1,2*n+1) cout<<sa[i]<<' ';cout<<endl;
//rep(i,1,2*n+1) cout<<sb[i]<<' ';cout<<endl;
//cout<<"begin"<<sa[n-n/4]<<' '<<sb[n-n/4]<<' '<<n-n/4<<endl;
if(sa[n-n/4]>=sb[n-n/4]) {
cout<<0<<endl;
continue;
}
int l=0,r=n;
while(l<r){
int mid=(r+l)>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
cout<<l<<endl;
}
return 0;
}
题意：
给出一个数组 A，求一个排列 B，使得，对于所有的 Bi 不等于 i ，且 Ai 与 Bi 相等的次数最多。
思路：
相等次数最多先直接贪心，把未被访问过的 Ai 都保存到 Bi 当中。需要统计相等的次数，该匹配次数即为最终结果次数。
求排列 B 就比较费心思，
如果全部匹配了，就输出数组 B ，
如果匹配数 cnt == n-1，即还有一个未被匹配，
如果剩余的空位和剩余的数字相等，就把该空位填上原本对应的 A 中的数字，然后将 B 中原本填着该 A 的位置填上剩余的数字。
如果不相等则直接把空位不上去。
如果匹配数 cnt < n-1，则必有一种方法可以使得剩余的数通过排列得到结果，详见代码46~73行。
代码：
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (register int i=a;i<n;i++)
const int N=2e5+5;
int t,n,a,b[N],aa[N],aaa[N];
bool vis[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
cin>>n;
memset(vis,0,sizeof(bool)*(n+1));
memset(b,0,sizeof(int)*(n+1));
int cntpp=0;
rep(i,1,n+1){
cin>>a;aa[i]=a;
if(!vis[a]){
vis[a]=1;
b[i]=a;
aaa[a]=i;
cntpp++;
}
}
if(cntpp==n){
cout<<n<<'\n';
rep(i,1,n+1) cout<<b[i]<<" ";
cout<<'\n';
continue;
}
if(cntpp==n-1){
int ss,sb;
rep(i,1,n+1) {
if(!vis[i]) ss=i;
if(!b[i]) sb=i;
}
if(ss==sb) {
b[sb]=aa[sb];
b[aaa[aa[sb]]]=ss;
}
else b[sb]=ss;
cout<<cntpp<<'\n';
rep(i,1,n+1) cout<<b[i]<<" ";
cout<<'\n';
continue;
}
int now=1;
int kj;
for(register int i=1;i<=n;++i){
if(b[i]==0){
while(vis[now]&&now<=n+1) ++now;
if(i!=now){
vis[now]=1;
b[i]=now;
kj=i;
//cout<<now<<"az\n";
}
else{
int tmp=now+1;
while(vis[tmp]&&tmp<=n+1) ++tmp;
if(tmp<=n){
vis[tmp]=1;
b[i]=tmp;
kj=i;
}
else{
b[i]=b[kj];
b[kj]=now;
vis[now]=1;
}
//cout<<tmp<<"666\n";
}
}
}
cout<<cntpp<<'\n';
rep(i,1,n+1) cout<<b[i]<<" ";
cout<<'\n';
}
return 0;
}