xtuoj-part2

Index

• Index
• 最小化
• 加一
• 删除
• Cow
• 分段
• 菱形
• 字符矩阵
• 矩形
• 积
• 数组

最小化

• 最小化

#include<stdio.h>

char num[1010];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        scanf("%s",num);
        if(num[0]=='1') k++;
        for(int i=1;i<n&&k>1;i++,k--){
            if(num[i]=='0'||num[i]==num[0]){
                k++;//当num等于第一个或者等于零时，不改变k值
            }
            else{
            for(int j=i+1;j<n;j++){//进入筛子，把相同的数字标记筛除
                if(num[j]==num[i]){
                    num[j]='0';
                    }
                }
                num[i]='0';
            }
        }
        for(int i=1;i<n;i++){//最后处理第一个值，如果提前处理，会破坏筛的过程
            if(num[i]==num[0]) num[i]='1';
        }
        num[0]='1';
        if(n==1) num[0]='0';
        printf("%s\n",num);
    }
    return 0;
}

加一

• 加一

举个例子

              *                 
              *
              * *
              * *
              * *   *       
    *         * *   *       
*   *   *     * *   *       
* * *   *     * * * * *     
* * * * *   * * * * * *     
3 2 4 1 3 0 1 9 7 2 5 2 

              *             0+3    
              *
              * *
              * *
              * *   *       
    *         * *   *       
*   *   * * * * *   *       
* * *   * * * * * * * *     
* * * * * * * * * * * *     
3 2 4 1 3 0 1 9 7 2 5 2 

              *             1+3
              *
              * *
              * *
              * *   *       
    * * * * * * *   *       
*   * * * * * * *   *       
* * * * * * * * * * * *     
* * * * * * * * * * * *     
3 2 4 1 3 0 1 9 7 2 5 2 

* * * * * * * *             2+7
* * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *   *       
* * * * * * * * *   *       
* * * * * * * * *   *       
* * * * * * * * * * * *     
* * * * * * * * * * * *   
3 2 4 1 3 0 1 9 7 2 5 2 

对于7 2 5 2 ，理解成为边界的外面，存在一个max=9

* * * * * * * *         *    情况和之前是一样的
* * * * * * * *         *
* * * * * * * * *       *
* * * * * * * * *       *
* * * * * * * * *   *   *    
* * * * * * * * *   *   *    
* * * * * * * * *   *   *    
* * * * * * * * * * * * *    
* * * * * * * * * * * * *   
3 2 4 1 3 0 1 9 7 2 5 2 9

然后就是观察规律了，或者直接模拟这个过程

#include<stdio.h>

int num[10010];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,max=-1e9;
        long long cnt=0;/* 注意long long */
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&num[i]);
            if(max<num[i]) max=num[i];
        }
        for(int i=0;i<n;i++){
            num[i]=max-num[i];
        }
        cnt=num[0];
        for(int i=0;i<n-1;i++){
            if(num[i+1]>num[i]) cnt+=num[i+1]-num[i];
        }
        printf("%lld\n",cnt);
    }
    return 0;
}

删除

• 删除

据说是签到题，所谓让我来就是签个到就走的题
归属于贪心，这个题很有意思，难度颇高，但是想出来后，其实也就那样，归属于思维题吧
下面对代码给出证明
首先证明升序(降序)必可压缩

对于三个数
$$
a_{1} \leq a_{2} \leq a_{3}
$$
有
$$
a_{2} - a_{1} \geq k \ a_{3} - a_{2} \geq k
$$
要证明
$$
\lfloor \frac{a_{1}+a_{2}}{2} \rfloor + k \geq \lfloor \frac{\lfloor \frac{a_{1}+a_{2}}{2} \rfloor + a_{3}}{2} \rfloor
$$
成立，先变形成
$$
\lfloor \frac{a_{1}+a_{2}}{2} + k \rfloor \geq \lfloor \frac{\lfloor \frac{a_{1}+a_{2}}{2} \rfloor + a_{3}}{2} \rfloor
$$
要证上式，先证下式成立，即
$$
\frac{a_{1}+a_{2}}{2} + k \geq \frac{\lfloor \frac{a_{1}+a_{2}}{2} \rfloor + a_{3}}{2}
$$
即
$$
a_{1}+a_{2} + 2k \geq \lfloor \frac{a_{1}+a_{2}}{2} \rfloor + a_{3}
$$
即
$$
2k \geq \lfloor \frac{a_{1}+a_{2}}{2} \rfloor -a_{1} + a_{3} - a_{2}
$$
因为
$$
a_{2} \geq \frac{a_{1}+a{2}}{2} \geq \lfloor \frac{a_{1}+a{2}}{2} \rfloor \geq a_{1}
$$
则上式放缩为
$$
2k \geq a_{2}-a_{1}+a_{3}-a_{2}
$$
为题设条件，故原式成立，单调下降时同理可证

然后证明，该从小到大处理得到的值是最大的

怎么理解这个呢

对于max数组和min数组，是从小到大，从大到小处理的
如果每个max数组和min数组里储存的是当前(前i个)情况的最大值(最小值)，那么就有：
如果max[i]和 min[i+1]的差不超过k，那么可以将前i个数合并成max[i]，后n-i个数合并成 min[i+1]
然后将它们合并成一个新的数

代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int arr[100010];
int max[100010];
int min[100010];
long long sup=1000000000;

int cmp(const void* a,const void* b){
    return *(int *)a-*(int *)b;
}

void getMax(int n,int k){
    max[0]=arr[0];
    for(int i=1;i<n;i++){
        if(max[i-1]+k<arr[i]){
            while(i<n) max[i++]=sup;
        }else{
            max[i]=(arr[i]+max[i-1])/2;
        }
    }
}
void getMin(int n,int k){
    min[n-1]=arr[n-1];
    for(int i=n-2;i>=0;i--){
        if(min[i+1]-k>arr[i]){
            while(i>=0) min[i--]=-sup;
        }else{
            min[i]=(arr[i]+min[i+1])/2;
        }
    }
}
int main()
{
    int n,k,i=0;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    qsort(arr,n,sizeof(int),cmp);
    getMax(n,k);
    getMin(n,k);
    if(min[0]!=-sup||max[n-1]!=sup) puts("Yes");
    else{
        for(i=0;i<n-1;i++){
            if(abs(max[i]-min[i+1])<=k){
                puts("Yes");
                break;
            }
        }        
    }
    if(i==n-1) puts("No");
    return 0;
}

Cow

• Cow

思路不难，但一直过不了，应该是统计方式的问题
错误原因竟是： 他看错题目了！！！

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define min(a,b) (a<b?a:b)

int cnt[300];

int cmp(const void *a,const void *b){
    return *(int *)b-*(int *)a;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,p,k,ans=0,sum=0;
        scanf("%d%d%d%d",&n,&m,&p,&k);
        for(int i=0;i<p;i++){
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1==x2){
                if(cnt[min(y1,y2)]==0) ans++;
                cnt[min(y1,y2)]++;//x相等的话，分割y
            }else{
                if(cnt[101+min(x1,x2)]==0) ans++;
                //把x和y放在一个数组，省去了合并数组排序的麻烦，一步到位
                cnt[101+min(x1,x2)]++;//y相等的话，分割x
            }
        }
        qsort(cnt,300,sizeof(int),cmp);//从大到小排序
        if(ans<=k) printf("0 %d\n",ans);
        else{
            for(int i=0;i<k;i++){
                sum+=cnt[i];
            }
            printf("%d\n",p-sum);
        }
        memset(cnt,0,sizeof(cnt));
    }
    return 0;
}

分段

• 分段
  简单，注意全部为零的情况

#include<stdio.h>
#include<stdlib.h>

#define N 100010

int num[N];
int fac[N];

int cmp(const void* a,const void *b){
    return *(int *)a-*(int *)b;
}

int main()
{
    int n,sum=0,index=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&num[i]);
        sum+=num[i];
    }
    for(int i=1;i*i<=sum;i++){
        if(sum%i==0) fac[index++]=i;
        if(i!=sum/i) fac[index++]=sum/i;
    }
    qsort(fac,index,sizeof(int),cmp);
    for(int i=0;i<=index;i++){/* 注意，如果不是i<=index，那么当输入全为0时，将无法输出，所以要加上=进行特判 */
        int cnt=0,temp=0;
        for(int j=0;j<n;j++){
            temp+=num[j];
            if(temp==fac[i]) cnt++,temp=0;
            else if(temp>fac[i]) break;
        }
        if(cnt*fac[i]==sum){
            printf("%d\n",fac[i]);
            break;
        }
    }
    return 0;
}

菱形

• 菱形
  找规律，我讨厌找规律

#include<stdio.h>
#include<string.h>

char canvas[23][23];

inline void rhombus(int x,int y){
	canvas[x][y]='/';
	canvas[x][y+1]='\\';
	canvas[x+1][y]='\\';
	canvas[x+1][y+1]='/';
}
int main()
{
	int  n;
	while(scanf("%d",&n),n){
		int m,i,j,k;
		for(m=1;m*m<n;m++);
		memset(canvas,' ',sizeof(canvas));
		for(i=k=0;i<m;i++){
			for(j=0;j<=i;j++){
				rhombus(i,m-i-1+j*2);//菱形的偏移量
				if(++k==n) goto end;
			}
		}
		for(i=0;i<m-1;i++){
			for(j=0;j<m-i-1;j++){
				rhombus(m+i,1+i+j*2);
				if(++k==n) goto end;
			}
		}
		end:
			for(i=0;i<2*m+1;i++){
				for(j=2*m+1;j>=0&&canvas[i][j]==' ';j--);
				canvas[i][j+1]=0;
				if(j==-1) break;
				puts(canvas[i]);
				
			}
	}
	return 0;
}

字符矩阵

• 字符矩阵
  给出证明：

-4 -3 -2 -1  0   |  0 -1 -2 -3 -4 
-3 -2 -1  0  1   |  1  0 -1 -2 -3
-2 -1  0  1  2   |  2  1  0 -1 -2
-1  0  1  2  3   |  3  2  1  0 -1
 0  1  2  3  4   |  4  3  2  1  0
   i+j-n+1       |       i-j
可以发现，这两个矩阵是对称的

0 1 2 1 0
1 0 1 0 1
2 1 0 1 2
1 0 1 0 1
0 1 2 1 0
min(|i-j|,|i+j-n+1|)

#include<stdio.h>
#include<math.h>
int min(int x, int y) {
	return x<y?x:y;
}
int main() {
	char c;
	while((c= getchar())!='#') {
		getchar();
		int i,j,n,x,y,d;
		n=(c-'A'+1)*2-1;
		for (i=0;i<n;i++) {
			for (j=0;j<n;j++) {
				x=abs(j-i);
				y=abs(i+j-n+1);
				d=min(x, y);
				putchar(c-d);
			}
			putchar('\n');
		}
	}
	return 0;
}

矩形

• 矩形

我还是太菜了。。。。

#include<stdio.h>
#include<stdlib.h>

typedef long long ll;
ll a[100010];

int cmp(const void* a,const void *b){
    return *(ll *)a-*(ll *)b;
}

ll cnt(int size,int area){
    int i=0,j=size-1;
    ll ans=0,t;
    while(i<j){
        t=area/a[i];
        while(j>=0&&a[j]>t) j--;//找到最大的满足小于area的数组下标
        if(j>i) ans+=j-i;
        i++;
    }
    return ans;
}

int shrink(int size){//去重
    int i,j;
    for(int i=0,j=1;j<size;j++){
        while(j<size&&a[j]==a[i]) j++;//一个用来查找，一个用作下标
        if(j<size) a[++i]=a[j];
    }
    return i+1;
}

int square(int size,ll L,ll R){//计算正方形数量
    int i,j,ans=0;
    ll s;
    for(int i=0,j=1;j<size;j++){
        while(j<size&&a[i]==a[j]) j++;//找到相同情况的最后一个下标
        if(j-i>1){//如果有正方形就进入
            s=1LL*a[i]*a[i];
            if(s>=L&&s<=R) ans++;
            if(s>R) return ans;//因为是从小到大排序的，大于就说明就算后面存在正方形，也不会满足
        }
        i=j;
    }
    return ans;
}

int main()
{
    int n,i;
    ll L,R,ans;
    scanf("%d%lld%lld",&n,&L,&R);
    for(int i=0;i<n;i++) scanf("%lld",a+i);
    qsort(a,n,sizeof(ll),cmp);
    ans=square(n,L,R);
    n=shrink(n);
    ans+=cnt(n,R)-cnt(n,L-1);//思路太清楚了QAQ
    printf("%lld\n",ans);
    return 0;
}

积

QAQ，一直在debug，思路不清楚，代码丑陋，如果有更好的解法，一定要拿过来看

• 积

#include<stdio.h>
#include<stdlib.h>

typedef long long  ll;
#define N 10010

ll a[N],b[N],c[N];

int cmp(const void *a,const void *b){
    return *(ll *)a-*(ll *)b;
}

ll mod(ll a){
    return a%(1000000007);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k,index_b=0,index_c=0;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++){
            scanf("%lld",&a[i]);
            if(a[i]<0) b[index_b++]=a[i];
            else c[index_c++]=a[i];
        }
        qsort(b,index_b,sizeof(ll),cmp);
        qsort(c,index_c,sizeof(ll),cmp);
        /* index_b+index_c==k */
        if(index_b+index_c==k){
            ll ans=1;
            while(k) ans*=a[--n],k--,ans=mod(ans);
            printf("%lld\n",ans);
            continue;
        }
        /* 全为正数 */
        if(index_b<2){
            ll ans=1;
            while(index_c,k) ans*=c[--index_c],k--,ans=mod(ans);
            printf("%lld\n",ans);
            continue;
        }
        /* 全为负数 */
        if(index_c==0){
            ll ans=1,i=0;
            if(k%2==0){
                while(i<k) ans*=b[i++],ans=mod(ans);
            }else{
                while(index_b,k) ans*=b[--index_b],k--,ans=mod(ans);
            }
            printf("%lld\n",ans);
            continue;
        }
        /* 有正有负 */
        int left=0,right=index_c-1;
        ll ans=1;
        while(k){
            if(k%2==0){
                while(k){
                    ll x=0,y=0;
                    if(right-2>=-1) y=c[right]*c[right-1];
                    if(left+2<=index_b) x=b[left]*b[left+1];
                    ans=mod(ans);
                    if(x>y) x=mod(x),ans*=x,left+=2;
                    else y=mod(y),ans*=y,right-=2;
                    ans=mod(ans);
                    k-=2;
                }
            }else{
                k--;
                ans*=mod(c[right--]);
                ans=mod(ans);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

找老师要了一份思路清楚的码

#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#include <vector>
const size_t N = 100011;
const long long mod = 1e9+7;
int a[N];

bool cmp(const int &a,const int &b){
	return std::abs(a) < std::abs(b);
}

long long min(int n,int k){
	std::sort(a,a+n,cmp);
	int i;
	long long ans = 1LL;
	for(i=0;i<k;i++) ans = ans * a[i] % mod;
	return ans;
}

long long max(int n,int k){
	int i,j;
	long long t1,t2,ans=1LL;
	std::sort(a,a+n);
	i = 0, j = n-1;
	if(k&1)	ans *= a[j--];
	if(ans < 0) return -1;
	for(k>>=1;k;k--){
		t1 = 1LL * a[i] * a[i+1];
		t2 = 1LL * a[j] * a[j-1];
		if(t1 < t2) {			
			ans = ans * (t2 % mod) % mod;
			j-=2;
		} else {			
			ans = ans * (t1 % mod) % mod;
			i+=2;
		} 
	}
	return ans;
}

void solve(){
	int n,k,i;
	scanf("%d %d",&n,&k);
	for(i=0;i<n;i++) scanf("%d",a+i);
	long long t;
	t = max(n,k);	
	if(t < 0) t = min(n,k);
	printf("%lld\n",t);
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

数组

• 数组

第一次体验到被卡常，wc，太痛苦了

#include<stdio.h>
#include<stdlib.h>
#define N 100010
typedef long long ll;
ll a[N];

int cmp(const void *a,const void *b){
    return *(ll *)a-*(ll *)b;
}

inline void init(ll n,ll m){
    for(ll i=2;i<n;i++){
        a[i]=(a[i-1]+a[i-2])%m;
    }
    qsort(a,n,sizeof(ll),cmp);
}

ll solve(ll n,ll max){
    ll ans=0,j=n-1;
    for(ll i=0;i<n;i++){
        while(i<=j&&a[i]+a[j]>max) j--;
        if(i<=j) ans+=j-i+1;
    }
    return ans;
}

int main()
{
    ll T,n,m,l,r,ans;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld %lld %lld %lld %lld %lld",&n,&a[0],&a[1],&m,&l,&r);
        init(n,m);
        ans=solve(n,r)-solve(n,l-1);
        printf("%lld\n",ans);
    }
    return 0;
}