A
排序，前缀和统计 \(\left[1,i\right]\) 内有多少不同数字，枚举 \(l\)，二分 \(r\)，显然的是 \(l,r\) 等于某一个数字最好，所以可以得到对于每个 \(l\)，最多有多少数字不被修改。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=4e5+10;
int n,x,a[N],ans,s[N];
void solve(){
read(n),read(x);
x*=8;
ans=n;
for(int i=1;i<=n;i++){
read(a[i]);
}
sort(a+1,a+n+1);
s[1]=1;
for(int i=2;i<=n;i++){
s[i]=s[i-1];
if(a[i]!=a[i-1]){
s[i]++;
}
}
for(int i=1;i<=n;i++){
int l=i,r=n,pos=n+1;
while(l<=r){
int mid=(l+r)>>1;
double y=ceil(log2(s[mid]-s[i]+1));
if(y*n<=x){
pos=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
ans=min(ans,n-(pos-i+1));
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
B
正着模拟不好处理，考虑反过来。
假设当前正在处理第 \(i\) 次操作，令它为操作 \(1\)。显然当后面有操作 \(1\) 时，该操作为无效操作。后面操作 \(2\) 的值的 \(\max\) 值 \(mx\) 会影响当前位置最终赋的值，所以将当前位置的值赋为 \(\max(mx,x)\)，并打上标记。对于到最后还没有被进行过操作 \(1\) 的位置，将值与 \(mx\) 取 \(\max\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,Q,a[N],tag[N];
struct node{
int opt,p,x;
}q[N];
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
}
read(Q);
for(int i=1;i<=Q;i++){
read(q[i].opt);;
if(q[i].opt==1){
read(q[i].p),read(q[i].x);
}
else{
read(q[i].x);
}
}
int mn=0;
for(int i=Q;i;i--){
if(q[i].opt==1){
if(!tag[q[i].p]){
tag[q[i].p]=1;
a[q[i].p]=max(q[i].x,mn);
}
}
else{
mn=max(mn,q[i].x);
}
}
for(int i=1;i<=n;i++){
if(!tag[i]){
a[i]=max(a[i],mn);
}
write_space(a[i]);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
C
对于一条边，如果两个端点都还没选，那么选择这条边和两个端点。被选择的边代表一个匹配，不被选择的点代表一个独立集。根据操作过程可知，其中必有一个大小大于等于 \(n\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
int n,m;
void solve(){
read(n),read(m);
set<int>s1,s2;
for(int i=1;i<=n*3;i++){
s1.insert(i);
}
for(int i=1,u,v;i<=m;i++){
read(u),read(v);
if(s1.count(u)&&s1.count(v)){
s1.erase(u),s1.erase(v);
s2.insert(i);
}
}
if(s1.size()>=n){
puts("IndSet");
int s=0;
while(s<n){
write_space(*s1.begin());
s1.erase(s1.begin());
s++;
}
}
else{
puts("Matching");
int s=0;
while(s<n){
write_space(*s2.begin());
s2.erase(s2.begin());
s++;
}
}
putchar('\n');
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
D
记 \(f_{xl,yl,xr,yr}\) 表示左上角为 \((xl,yl)\)，右下角为 \((xr,yr)\) 的矩形的答案，记忆化搜索即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=60,inf=0x3f3f3f3f;
int n,f[N][N][N][N];
char ch[N][N];
int dfs(int xl,int yl,int xr,int yr){
if(f[xl][yl][xr][yr]!=inf){
return f[xl][yl][xr][yr];
}
if(xl==xr&&yl==yr){
f[xl][yl][xr][yr]=(ch[xl][yl]=='#');
return f[xl][yl][xr][yr];
}
for(int i=xl;i<xr;i++){
f[xl][yl][xr][yr]=min(f[xl][yl][xr][yr],dfs(xl,yl,i,yr)+dfs(i+1,yl,xr,yr));
}
for(int i=yl;i<yr;i++){
f[xl][yl][xr][yr]=min(f[xl][yl][xr][yr],dfs(xl,yl,xr,i)+dfs(xl,i+1,xr,yr));
}
f[xl][yl][xr][yr]=min(f[xl][yl][xr][yr],max(xr-xl+1,yr-yl+1));
return f[xl][yl][xr][yr];
}
void solve(){
memset(f,inf,sizeof(f));
read(n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ch[i][j]=getchar();
while(ch[i][j]!='.'&&ch[i][j]!='#'){
ch[i][j]=getchar();
}
}
}
write_endl(dfs(1,1,n,n));
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
E
第一下看错了题，以为和D是一样的题意，只是放大了数据，仔细一看发现贡献从矩形两边的最大值变成了最小值。这样，每次选择的矩形变成了 \(1\times \infty\) 或 \(\infty\times 1\)。题意变成了可以选择一些行和一些列，覆盖到所有矩形，并使所选行和列的数量之和最少。对于一个矩形，它要么选择所有的行，要么选择所有的列，将行和列之间连边，就变成了二分图最大匹配问题了。
但这不够，考虑离散化，将矩形的右边界和下边界拓宽一格，这时矩形被表示为了 \([xl,xr),[yl,yr)\)。令离散化后的直线 \(x_i,y_i\) 表示 \([x_i,x_{i+1}),[y_i,y_{i+1})\) 这个区间。很容易发现这和原来的二分图匹配仍然等价，因为一个区间里直线要么全选，要么全不选。将原来在一个矩形里的两条线连边，跑网络流即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=210,inf=1e9,M=2e5+10;
int x[N],y[N],n,m,cntx,cnty;
struct node{
int xl,xr,yl,yr;
}mat[N];
int head[N],S,T,tot=1,dep[N],cur[N];
struct edge{
int v,w,nxt;
}e[M];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
bool bfs(int S,int T){
for(int i=1;i<=T;i++){
dep[i]=0;
}
queue<int>q;
q.push(S);
dep[S]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&!dep[v]){
dep[v]=dep[u]+1;
if(v==T){
return 1;
}
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int flow,int T){
if(u==T){
return flow;
}
int s=0;
for(int i=cur[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&dep[v]==dep[u]+1){
int res=dfs(v,min(flow,w),T);
e[i].w-=res;
e[i^1].w+=res;
s+=res;
flow-=res;
}
if(!flow){
break;
}
}
if(!s){
dep[u]=0;
}
return s;
}
int dinic(int S,int T){
int sum=0;
while(bfs(S,T)){
for(int i=1;i<=T;i++){
cur[i]=head[i];
}
sum+=dfs(S,inf,T);
}
return sum;
}
void solve(){
read(n),read(m);
for(int i=1;i<=m;i++){
read(mat[i].xl),read(mat[i].yl),read(mat[i].xr),read(mat[i].yr);
mat[i].xr++,mat[i].yr++;
x[++cntx]=mat[i].xl,x[++cntx]=mat[i].xr;
y[++cnty]=mat[i].yl,y[++cnty]=mat[i].yr;
}
sort(x+1,x+cntx+1);
sort(y+1,y+cnty+1);
cntx=unique(x+1,x+cntx+1)-x-1;
cnty=unique(y+1,y+cnty+1)-y-1;
for(int i=1;i<=m;i++){
mat[i].xl=lower_bound(x+1,x+cntx+1,mat[i].xl)-x;
mat[i].xr=lower_bound(x+1,x+cntx+1,mat[i].xr)-x;
mat[i].yl=lower_bound(y+1,y+cnty+1,mat[i].yl)-y;
mat[i].yr=lower_bound(y+1,y+cnty+1,mat[i].yr)-y;
for(int j=mat[i].xl;j<mat[i].xr;j++){
for(int k=mat[i].yl;k<mat[i].yr;k++){
add(j,k+cntx,inf);
add(k+cntx,j,0);
}
}
}
S=cntx+cnty+1,T=cntx+cnty+2;
for(int i=1;i<cntx;i++){
add(S,i,x[i+1]-x[i]);
add(i,S,0);
}
for(int i=1;i<cnty;i++){
add(i+cntx,T,y[i+1]-y[i]);
add(T,i+cntx,0);
}
write_endl(dinic(S,T));
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
F
令两组的 \(\gcd\) 分别为 \(g_1,g_2\)。
先假设已知放数的顺序，怎么放是最优的。有一个贪心的想法，假如 \(g_1\) 是 \(a_i\) 的因子，那么放到第一组里肯定不会是 \(g_1\) 变小，所以将 \(a_i\) 放到第二组后肯定不劣于放到第一组。
所以我们随机放数顺序，当随机一定多组后还不行，则答案为NO。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int n,a[N],id[N],g[2],ans[N];
bool work(){
ans[id[1]]=1;
g[1]=a[id[1]];
ans[id[2]]=2;
g[2]=a[id[2]];
for(int i=3;i<=n;i++){
if(a[id[i]]%g[1]){
ans[id[i]]=1;
g[1]=__gcd(a[id[i]],g[1]);
}
else{
ans[id[i]]=2;
g[2]=__gcd(a[id[i]],g[2]);
}
}
return (g[1]==1)&&(g[2]==1);
}
void solve(){
srand((unsigned)time(NULL));
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
id[i]=i;
}
int T=min(500,10000000/n/2);
while(T--){
random_shuffle(id+1,id+n+1);
if(work()){
puts("YES");
for(int i=1;i<=n;i++){
write_space(ans[i]);
}
return;
}
}
puts("NO");
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}