头像

沄逸




离线:12小时前


最近来访(130)
用户头像
Pr
用户头像
Snowandraw.
用户头像
seeingsomeone
用户头像
用户头像
RyanMoriarty
用户头像
就是玩儿
用户头像
冷冷月光
用户头像
山海皆可平
用户头像
@Moli
用户头像
猪啊猪
用户头像
封禁用户
用户头像
Peter_5
用户头像
Linclon
用户头像
Laurus_1
用户头像
离幻
用户头像
h111111
用户头像
大风大雪
用户头像
刷刷刷算法
用户头像
姚军
用户头像
啦_7

活动打卡代码 AcWing 796. 子矩阵的和

沄逸
12小时前
#include<iostream>

using namespace std;

const int N=1010;
int a[N][N],s[N][N];

int main()
{
  int n,m,q;
  cin >> n >>m >> q;
  for(int i=1;i<=n;i ++)
    for(int j=1;j<=m;j ++)
      cin >> a[i][j];
  // 初始化前缀和
  for(int i=1;i<=n;i ++)
    for(int j=1;j<=m;j ++)
      s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
  //询问
   while(q--)
   {
       int x1,x2,y1,y2;
       cin >> x1 >> y1 >> x2 >> y2;
       cout << s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] << endl;
   }
   return 0;
}


活动打卡代码 AcWing 795. 前缀和

沄逸
12小时前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int a[N];
int s[N];
int n,m;

signed main()
{
   cin >> n >> m;
   for(int i=1;i<=n;i ++)
   {
       cin >> a[i];
       s[i]=s[i-1]+a[i];
   }
   while(m--)
   {
       int l,r;
       cin >> l >> r;
       cout << s[r]-s[l-1] << endl;
   }
    return 0;
}




活动打卡代码 AcWing 1227. 分巧克力

沄逸
14小时前
#include<iostream>

using namespace std;

const int N=100010;
int w[N],h[N];//存储长、宽
int n,k;

bool chack(int mid)
{
    int res=0;//记录分成长度为 mid 的巧克力数量
    for(int i=0;i<n;i ++)
    {
        res+=((long long)h[i]/mid)*((long long)w[i]/mid);//每一大块可以分成的边长为 mid 的巧克力数量
    }
     if(res>=k)return true;//大于要求数量,返回真
      return false;
}

int main()
{

    cin >>  n >> k;
    for(int i=0;i<n;i ++)
    {
        cin >> h[i] >> w[i];
    }
    int l=1,r=1e5;//小巧克力数量边长一定在 1 -- 100000 之间
    while(l<r)//二分小巧克力边长范围,找到符合要求的最大值
    {
        int mid=(l+r+1)/2;
        if(chack(mid))l=mid;
        else
          r=mid-1;
    }
    cout << r << endl;
    return 0;
}



活动打卡代码 AcWing 1221. 四平方和

沄逸
15小时前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=5e6+100,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

struct Sum
{
    int s,c,d;
    bool operator < (const Sum &t)const
    {
        if(s!=t.s)return s<t.s;
        if(c!=t.c)return c<t.c;
        if(d!=t.d)return d<t.d;
    }
}sum[N];

int n,m;

signed main()
{

   cin >> n;
   for(int c=0;c*c<=n;c ++)
   {
       for(int d=c;c*c+d*d<=n;d ++)
       {
           sum[m++]={c*c+d*d,c,d};
       }
   }
   sort(sum,sum+m);

   for(int a=0;a*a<=n;a ++)
   {
       for(int b=a;b*b+a*a<=n;b ++)
       {
           int t=n-a*a-b*b;
           int l=0,r=m-1;
           while(l<r)
           {
               int mid=(l+r)/2;
               if(sum[mid].s>=t)r=mid;
               else l=mid+1;
           }

           if(sum[l].s==t)
           {
               cout << a <<' '<< b << ' ' << sum[l].c << ' ' << sum[l].d << endl;
               return 0;
           }
       }

   }

    return 0;
}




活动打卡代码 AcWing 1978. 奶牛过马路

沄逸
17小时前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n;
PII  q[N];
int smax[N],smin[N];

signed main()
{
    cin >> n;
    for(int i=1;i<=n;i ++)
    {
        cin >> q[i].x >> q[i].y;
    }
    sort(q+1,q+1+n);

    //前缀最值
    smax[0]=-INF,smin[n+1]=INF;
    for(int i=1;i<=n;i ++)
    {
        smax[i]=max(smax[i-1],q[i].y);
    }
    for(int i=n;i>=1;i --)
    {
        smin[i]=min(smin[i+1],q[i].y);
    }
    int res=0;
    for(int i=1;i<=n;i ++)
    {
        if(smax[i-1]<q[i].y && smin[i+1]>q[i].y)//该点之前的最大值必须小于q[i].y,之后的最小值必须大于q[i].y
          res++;
    }
    cout << res << endl;
    return 0;
}




活动打卡代码 AcWing 1987. 粉刷栅栏

沄逸
18小时前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

map<int,int> mp1;

signed main()
{
    int n,a=0,b;
    char c;
    cin >>  n;
    for(int i=0;i<n;i ++)
    {
        cin >> b >> c;
        //向右走就+b
        if(c=='R')
        {
            mp1[a]++;
            mp1[a+b]--;
            a+=b;
        }
        //向左走就 -b
        else
        {
            mp1[a-b]++;
            mp1[a]--;
            a-=b;
        }
    }
    int sum=0,ans=0,L;
     for(auto [k, v] : mp1)
     {
        // debug3(k, v, sum);
        if(sum <= 1 && sum + v > 1) L = k; //如果sum 从比2小变到比2大,那么k值就是区间左端点
        else if(sum > 1 && sum + v <= 1) ans += k - L; //反之就是区间右端点
        sum += v;//更新sum 的值
    }
    cout << ans << endl;

    return 0;
}




活动打卡代码 AcWing 1996. 打乱字母

沄逸
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010;

int n;
string a[N], b[N], c[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        b[i] = c[i] = a[i];
        sort(b[i].begin(), b[i].end(), greater<char>());//b取最大,倒序
        sort(c[i].begin(), c[i].end());//c取最小
    }

    sort(b + 1, b + n + 1);
    sort(c + 1, c + n + 1);

    for (int i = 1; i <= n; i ++ )
    {
        sort(a[i].begin(), a[i].end());
        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (b[mid] >= a[i]) r = mid;
            else l = mid + 1;
        }

        cout << r << ' ';
        reverse(a[i].begin(), a[i].end());
        l = 1, r = n;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (c[mid] <= a[i]) l = mid;
            else r = mid - 1;
        }

        cout << r << endl;
    }

    return 0;
}





沄逸
1天前

A - Not Shading 题目

代码:

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=55,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char g[N][N];
int n,m,r,l;

void solve()
{
    bool st=false;
    cin >> n >> m >>r >> l;
    //判断是否全是W;
    for(int i=1;i<=n;i ++)
    {
        for(int j=1;j<=m;j ++)
        {
            cin >> g[i][j];
            if(g[i][j]=='B')
                st=true;
        }
    }
    //如果都是W就输出-1;
    if(st==false)
    {
        cout << -1 << endl;
        return ;
    }
    //如果当前位置是B,就输出0;
    if(g[r][l]=='B')
    {
        cout << 0 << endl;
        return ;
    }
    else
    {
        //判断该位的行或者列有无B,如果有就输出1;
        for(int i=1;i<=m;i ++)
        {
            if(g[r][i]=='B')
            {
                cout << 1 << endl;
                return ;
            }
        }
        for(int i=1;i<=n;i ++)
        {
            if(g[i][l]=='B')
            {
                cout << 1 << endl;
                return ;
            }
        }
    }
    //都没有就输出2;
    cout << 2 << endl;
    return ;
}

signed main()
{

    int T;
    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}



思路:
第一题题面有点长,需要仔细阅读,可得知如果该行有B就可以使该行上的都变成B,也可以选择使该列都变成B,问最少的操作次数。可分析得知,如果都为W,则无法使其位置上变为B,则输出-1;如果该位上已经是B,则输出0;如果该位的行或列有B,则输出1;否则输出2。

B - Not Sitting 题目

代码:

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

vector<int>v;
int n,m;
void solve()
{
    cin>>n>>m;
    v.clear();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            v.push_back(max({i+j-2,i-1+m-j,n-i+j-1,n+m-i-j}));//(1,1),(1,m),(n,1),(n,m);
    sort(v.begin(),v.end());
    for(auto x:v)cout<<x<<' ';
    cout<<endl;     
}

signed main()
{

    int T;
    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}


思路:
由题可知R想要靠近T,但T想远离R,可得出结论,T只会坐四个角落,然后枚举一遍R的位置并计算两个位置最大的距离。存下来后sort一遍就是答案。

C - Not Assigning 题目

代码:

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n;
int ans[N];
vector<PII>v[N];
int ok;
int d[N];
void dfs(int u,int fa,int q)
{
    for(auto t:v[u])
    {
        if(t.x==fa)continue;
        ans[t.y]=q;
        if(q==2)dfs(t.x,u,3);
        else dfs(t.x,u,2);
    }
}

void solve()
{
    ok=1;
    cin>>n;
    for(int i=1;i<=n;i++)v[i].clear(),d[i]=0;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        d[a]++,d[b]++;
        if(d[a]>=3||d[b]>=3)ok=0;
        v[a].push_back({b,i});
        v[b].push_back({a,i});
    }
    for(int i=1;i<=n;i++)
    {
        if(d[i]==1&&ok)
        {
            dfs(i,-1,2);
            break;
        }
    }
    if(!ok)cout<<-1;
    else
    {
        for(int i=1;i<n;i++)cout<<ans[i]<<' ';
    }
    cout<<endl;

}

signed main()
{

    int T=1;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

思路:首先我们要确保这个树能组成一个链,此外权重分别为x,y,z,必须满足x、y 和 z 本身必须是素数并且x+y、y+z 和 x+z 也需要是素数。
由于 x,y,z≥2(因为 2 是最小的素数),所以 x+y,x+z,y+z≥4,所以它们一定是奇素数。这意味着:
x 和 y 具有相反的奇偶性。
y 和 z 具有相反的奇偶性。
x 和 z 具有相反的奇偶性。
因此,从任何叶节点开始一个 DFS,我们可以交替分配权重 2 和 3(或 2和任何孪生素数对的第一个数)以形成素数树。

D - Not Adding 题目

代码:

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e6+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n,ans;
int a[N];
int f[N];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],f[a[i]]++;//f数组记录该数出现的次数
    for(int i=N;i>=1;i--)
        if(!f[i]){
            int cnt=0;
            for(int j=i;j<=1e6;j+=i){
                if(f[j])
                    cnt=gcd(cnt,j);
            }
            if(cnt==i)ans++;
        }
    cout<<ans<<endl;
}

signed main()
{

    int T=1;
    while(T--)
        solve();
    return 0;
}

思路:
题目大致是在给定n个数里面可以任选两个数x,y;如果gcd(x,y) 在数组中没有出现过,就可以把这个数加到数组里面去。再操作下一次,直到不能再操作为止。问你最多可以操作多少次。




沄逸
2天前

A - Ancient Civilization 链接

代码:

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int n,m;
int a[50];
int b[110];
int c[110][110];
void solve()
{
    memset(c,0,sizeof c);
    memset(a,0,sizeof a);
    //n是数字个数,m是最大数字转化为2进制时的位数
    cin >> n >>m;
    for(int i=1;i<=n;i ++)
        cin >> b[i];
    int t=0;
    for(int i=1;i<=n;i ++)
    {
        int cnt=1;
        t=b[i];
        while(t>0)
        {
            c[i][cnt]=t%2;
            cnt++;
            t/=2;
            if(t==0)
              break;
        }
    }

    int ans=0;
    //a数组记录当前这位上的答案
    for(int j=1;j<=m;j ++)
    {
        int sum=0;//sum记录的是当前这位上1的个数
        for(int i=1;i<=n;i ++)
        {
            sum+=c[i][j];

        }
        //选取多的那个数字
        if(sum>n/2)
           a[j]=1;
    }
    //将数组a转化成答案
    for(int i=1;i<=m;i ++)
    {
        int k=i;
        if(a[k]==1)
        {
          ans+=pow(2,k-1);
        }
    }
    cout << ans << endl;
}

signed main()
{

    int T;
    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}

思路:
因为每一位都可以独立解决,所以只要把给定的这些数字都转化为2进制,再每一位进行比较,看是当前这位上0多还是1多,选取多的,再由选出来的2进制转化为10进制就是答案。
题外话:
本来一开始想的是写成一维,用秦九韶算法,但写到最后一步转化成答案有点不熟练,就重新推翻用二维写,有无巨巨帮忙瞅瞅,在线等!

B - Elementary Particles 链接

代码:

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=150100,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n;
int a;
void solve()
{
    int ans=-1;
    map<int,int> q;
    q.clear();
    cin >> n;
    for(int i=1;i<=n;i ++)
    {
        cin >> a;
        if(q[a])
            ans=max(ans,n-i+q[a]);
        q[a]=i;
    }
    cout << ans << endl;

}

signed main()
{

    int T;
    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}

思路:
每次都记录一下当前数字出现的位置,并查看是否之前出现过;假设上一次出现的位置为i,这次出现的位置为j,取max(i-j+n)。
因为数据范围给的过大,所以两重循环肯定会T,这里就需要用到map记录数字出现的位置并查看有无出现过。这样就可以做到线性。

C - Road Optimization 题目

#include <bits/stdc++.h>
using namespace std;

const int N = 500 + 5;
int dp[N][N], d[N], a[N];
const int INF =0x3f3f3f3f;

int main() {
  int n, l, k;
  cin >> n >> l >> k;
  for (int i = 0; i < n; i++) cin >> d[i];
  d[n] = l;
  for (int i = 0; i < n; i++) cin >> a[i];

  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      dp[i][j] = INF;
    }
  }
  dp[0][0] = 0;

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      for (int K = 0; K < i; K++) if (j >= (i-K-1)) {
        dp[i][j] = min(dp[i][j], dp[K][j-(i-K-1)] + (d[i] - d[K]) * a[K]);
      }
    }
  }

  int ans = INF;
  for (int j = 0; j <= k; j++) {
    ans = min(ans, dp[n][j]);
  }

 cout << ans << endl;
  return 0;
}

思路:
我们可以推出公式:dp(0,0)=0, dp(i,0)=dp(i−1,0)+b(i−1)⋅(ai−a(i−1))
首先,我们令dp(i,j)=0x3f;然后答案是min(dp(n,j)), (0<=j<=k);

for (int i = 0; i < n; i)
for (int j = 0; j <= k; j
)
{
如果我们看到 dp(i,j)=0x3f,那么没有答案,我们将跳过这个状态。现在,迭代我们将放置的下一个符号的位置。称这个位置为pos。结合上面公式可以得出dp(pos,j+pos-i-1)=min(dp(pos,j+pos-i-1),dp(i,j)+bi*(apos-ai))。
}



活动打卡代码 AcWing 2005. 马蹄铁

沄逸
2天前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n;
char g[N][N];
bool st[N][N];
int ans;

void dfs(int x,int y,int cntl,int cntr)
{
    st[x][y]=true;
    if(cntl==cntr)
    {
        ans=max(ans,cntl+cntr);
        st[x][y]=false;
        return ;
    }
    for(int i=0;i<4;i ++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0 && a<n && b>=0 && b<n && !st[a][b])
        {
            if(g[x][y]==')' &&g[a][b]=='(')continue;
            if(g[a][b]=='(') dfs(a,b,cntl+1,cntr);
            else dfs(a,b,cntl,cntr+1);
        }
    }
    st[x][y]=false;
}
signed main()
{

  cin >> n;
  for(int i=0;i<n;i ++)
    cin >> g[i];
  if(g[0][0]=='(')
  {
      dfs(0,0,1,0);
  }
  cout << ans << endl;
    return 0;
}