CF 日常1200

CF 1200题单
Stone Age Problem
Card Trick
Dolce Vita
Make it Increasing
2-Letter Strings
Wrong Addition

题解

Stone Age Problem 题目大意：

每次询问修改后求数组的和。
两种询问方式，第一种是修改X位置上的值，第二种是修改数组所有的值。

思路

这题线段树可以写，但是1200的题可能太复杂了，直接简单思路，利用set先存储每个位置。
每次修改：
当type=1时
修改该位置在set的里面则没有经过type2的修改 *** 作，直接sum=sum-a[x]+y。
若该位置不在set里说明位置上的值还是上次经过type2 *** 作的值，直接sum=sum-tmp+y,并把该位置添加到set中。

当type=2时：
更新tmp的值，sum=数组长度*更新的值；
清空set；
注意：数值比较大，必须记得开long long ;

#include
using namespace std;
const int N=200010;
typedef long long ll;
int n,m;
ll a[N];
int tot;
set<int>s;
int main()
{
 ll sum=0ll;
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)
   { 
   cin>>a[i],sum+=a[i];
     s.insert(i);
   }
   ll tmp=0;
 while(m--)
 {
     ll x,y,t;
     cin>>t;
     if(t==1)
     {
         cin>>x>>y;
         if(s.count(x))
         {
         sum=sum-a[x]+y;
         a[x]=y;
         printf("%lld\n",sum);
         }
         else
         {
            sum=sum-tmp+y;;
            a[x]=y;
             printf("%lld\n",sum);
             s.insert(x);
         }
     }
     else{
         cin>>x;
         tmp=x;
         sum=1ll*n*x;
         printf("%lld\n",sum);
         s.clear();

     }
 }
 return 0;
}

Card Trick 题目大意

交换ai和aj,bi和bj ,让a数组和b数组成非降序排列，若不能实现则输出-1，若能 则输出交换步骤

思路

前面可以先判定特殊的情况，直接可以输出。
输出交换步骤则可以想到冒泡排序法，冒泡排序时先比较a数组，则a数组相同时就比较b数组，比较时并保存答案方便最后输出。

#include
using namespace std;
const int N=1010;
int a[N];
int b[N];
int n,m;
struct node
{
    int a,b;
    bool operator <(const node &W) const
    {
        if(a==W.a) return b<W.b;
        return a<W.a;
    }
}e[N],ne[100010];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
             scanf("%d",&b[i]);
        for(int i=1;i<=n;i++)
        e[i]={a[i],b[i]};
        int ans=0;
        for(int i=1;i<n;i++)
        {
            if((e[i].a>e[i+1].a)||(e[i].b>e[i+1].b))
            {
                ans=1;
                break;
            }

        }
        if(!ans)
        {
            printf("%d\n",ans);
            continue;
        }
        sort(e+1,e+1+n);
        bool flag=true;
        for(int i=1;i<n;i++)
        {
            if((e[i].a>e[i+1].a)||(e[i].b>e[i+1].b))
            {
                flag=false;
                break;
            }

        }
        if(!flag)
        {
            printf("-1\n");
            continue;
        }
        int k=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n-i;j++)
            {
                if(a[j]>a[j+1]){
                    swap(a[j],a[j+1]);
                    swap(b[j],b[j+1]);
                    ne[++k]={j,j+1};
                }else if(a[j]==a[j+1])
                {
                    if(b[j]>b[j+1])
                    {
                        swap(b[j],b[j+1]);
                        ne[++k]={j,j+1};
                    }
                }
            }

        }
        printf("%d\n",k);
        for(int i=1;i<=k;i++)
        {
            printf("%d %d\n",ne[i].a,ne[i].b);
        }

    }
    return 0;
}

Dolce Vita 题目大意：

有n种商店，我们要到每种商店去买糖果，每个商店都有自己的价格，我们每天必须买一种糖果，如果无法购买则输出购买的糖果总数。商店糖果的价格是每天递增1元钱；

思路

简单的数学水题，我们可以先贪心找出最便宜的糖果是否超出我们的金额，是的话直接输出答案。
贪心完之后就是一个数学公式；
第一种糖果的购买数量为
sum+= a[1]+day<=coin;
sum++，加上第一天的数量。
第二种：
sum+=(a[1]+a[2])+2day<=coin;
sum++;
以此类推。
第i种
sum+=（a[1]+a[2]+…+a[i])+(iday)<=coin;
若（a[1]+a[2]+…+a[i])>coin 直接break；输出答案即可。
大数据开longlong

#include
using namespace std;
const int N=200010;
typedef long long ll;
ll a[N];
ll n,m;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll sum=0;
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;i++)
         scanf("%lld",&a[i]);
        sort(a+1,a+1+n);
        if(a[1]>m)
        {
            printf("0\n");
            continue;
        }
    ll   ans=0;
        for(int i=1;i<=n;i++)
        {
           
            ans+=a[i]; 
            if(ans>m) break;
            ll t=(m-ans)/(i);
            t++;
            sum+=t;
        }
        printf("%lld\n",sum);
        
    }
    return 0;
}

Make it Increasing 思路

枚举每个点作为特殊点的最小步骤

#include
using namespace std;
typedef long long ll;
const int N=200010;
ll a[N];
int n,m;
ll b[N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     cin>>a[i];long long  res=0;
     long long  ans=1e18;
     for(int pos=1;pos<=n;pos++)
     {
         memset(b,0,sizeof b);
         res=0;
         //left
         for(int i=pos-1;i>=1;i--)
         {
             ll t=b[i+1]-b[i];
             ll k=(a[i]+t)/a[i];
             b[i]=k*a[i];
             res+=k;
         }
         
         //right
         for(int i=pos+1;i<=n;i++)
         {
             ll t=b[i-1]-b[i];
             ll k=(a[i]+t)/a[i];
             b[i]=k*a[i];
             res+=k;
         }
         
         ans=min(res,ans);
         
     }
     cout<<ans<<endl;
    return 0;
}

2-Letter Strings 题目大意

找出字符串中只有一个字符相等的数量 。
水题

#include
using namespace std;
const int N=100010;
int a[26][26];
int n,m;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(a,0,sizeof a);
       cin>>n;
        char x,y;
        long long  ans=0;
       for(int j=0;j<n;j++)
		{
			cin>>x>>y;
			x=x-'a';
			y=y-'a';
			for(int i=0;i<='k'-'a';i++)
			{
				if(i!=y) ans+=a[x][i];
				if(i!=x) ans+=a[i][y];
			}
			a[x][y]++;
		}
        cout<<ans<<endl;
        
    }
    return 0;
}

Wrong Addition

水题自己理解

#include
using namespace std;
const int N=100010;
typedef long long ll;
char a[N],str[N];
int n,m;
int b[N],s[N],c[N];

int main()
{
    
    int T;
    cin>>T;
    while(T--)
    {
        memset(c,0,sizeof c);
        memset(b,0,sizeof b);
        memset(s,0,sizeof s);
        cin>>a>>str;
        bool flag=true;
        int len1=strlen(a);
        int len2=strlen(str);
        for(int i=0;i<len1;i++)
        {
            b[len1-i]=a[i]-'0';
        }
        for(int i=0;i<len2;i++)
        {
            s[len2-i]=str[i]-'0';
        }
        int j=1;int k;
        for(int i=1;i<=len1;i++)
        { 
            k=i;
            if(j>len2) 
            {
                flag=false;
                break;
            }
            if(b[i]>s[j])
            {
                int y=s[j]+s[j+1]*10;
                int x=y-b[i];
                if(x<0||x>10)//两位数减完之后不能为负数，不可能超过两位数
                {
                    flag=false;
                    break;
                }
                c[i]=x;
                j+=2;
                continue;
            }
            if(b[i]==s[j])
            {
                c[i]=0;
                j++;
                continue;
            }
            if(b[i]<s[j])
            {
                c[i]=s[j]-b[i];
                j++;
                continue;
            }
           
        }
       // cout<
        if(!flag)
        {
            cout<<"-1\n";
            continue;
        }
        if(j<=len2)
        {
            for(int i=j;i<=len2;i++)
                c[++k]=s[i];
        }
        for(int i=k;i>=1;i--)
        {
            if(c[i]!=0) {j=i;break;}
        }
        for(int i=j;i>=1;i--)
        printf("%d",c[i]);
        printf("\n");
    }
    return 0;
}