头像

温柚子




离线:1天前


最近来访(97)
用户头像
77an
用户头像
JimmyHu
用户头像
wz5280
用户头像
梦忆晴天
用户头像
A越努力越幸运
用户头像
Soul-Pe
用户头像
用户头像
Snow_raw
用户头像
浅安时光
用户头像
008
用户头像
ohmygod
用户头像
Rookie_
用户头像
初闇
用户头像
zzq12138
用户头像
Verse
用户头像
bingtong666
用户头像
charley123
用户头像
mcj201314
用户头像
superjava
用户头像
朱玉玺


题意:在一个圆上有n个点和链接两个点的一座桥,每个点在不同月份有不同的权值。要求回答q次询问每次询问给出月份m和两个点u,v,要求输出起点为u,终点为v的经历每个点仅一次的权值最大路径。

用c++写的

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 100010;

int n,m,p,q,month;  //n表示有n棵花树,m为观赏方案的种类,p和q之间有一座桥
int a[13][N];
int hh[13][N];  //hh[13][N]为前缀和,用来求u到v途中经过的开花的树的数量

int len(int u,int v)  //len(u,v)为u按顺时针方向走到v的途中经过的开花的树的数量
{
    if (u <= v)  return hh[month][v] - hh[month][u - 1];
    else return hh[month][n] - hh[month][u - 1] + hh[month][v];
}

void solve()
{
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        if (x == 1)
        {
            a[1][i]++;
            a[2][i]++;
            a[3][i]++;
        }
        else if (x == 2)
        {
            a[3][i]++;
            a[4][i]++;
        }
        else if (x == 3)
        {
            a[4][i]++;
            a[5][i]++;
        }
        else if (x == 4)
        {
            a[9][i]++;
            a[10][i]++;
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 12; j++)
            hh[j][i] = hh[j][i - 1] + a[j][i];  //前缀和

    scanf("%d%d%d", &p, &q, &m);
    if (p > q) swap(p, q);
    for (int i = 1; i <= m; i++)
    {
        int u, v, ans;
        scanf("%d%d%d", &month, &u, &v);
        if (u > v)  swap(u, v);
        bool flag = (u > p && u < q);
        bool check = (v > p && v < q);
        if (u == p || u == q || v == p || v == q) //只要有点在桥上面时一定不走桥最优
            ans = max(len(u, v), len(v, u));
        else if (flag && check)  //两点处同一区域时一定不走桥最优
            ans = max(len(u, v), len(v, u));
        else if(!flag && !check) //两点处同一区域一定不走桥最优
            ans = max(len(u, v), len(v, u));
        else if (flag)  //u,v在桥两边且u > p && u < q
            ans = max({len(u, v), len(v, u), len(q, v) + len(p, u), len(u, q) + len(v, p)});
        else if (check)  //u,v在桥两边且v > p && v < q
            ans = max({len(u, v), len(v, u), len(u, p) + len(v, q), len(q, u) + len(p, v)});
        if (ans)
            printf("%d\n", ans);
        else
            printf("So Sad.\n");
    }
}

int main()
{
    while (scanf("%d", &n) == 1)
    {
        solve();
    }
    return 0;
}

用c语言写的

#include<stdio.h>

int n,m,p,q,month;  //n表示有n棵花树,m为观赏方案的种类,p和q之间有一座桥
int a[13][100010];  //a[month][i]表示点i在month月的权值
int hh[13][100010];  //hh[month][i]表示点1~i在month月的权值和,用前缀和思想来求u到v途中经过的开花的树的数量

void swap(int x,int y)
{
    int k = 0;
    k = p;
    p = q;
    q = k;
}

int len(int u,int v)  //len(u,v)为u按顺时针方向走到v的途中经过的开花的树的数量(权值和)
{
    if (u <= v)  return hh[month][v] - hh[month][u - 1];
    else return hh[month][n] - hh[month][u - 1] + hh[month][v];
}

void solve()
{
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        if (x == 1)
        {
            a[1][i]++;
            a[2][i]++;
            a[3][i]++;
        }
        else if (x == 2)
        {
            a[3][i]++;
            a[4][i]++;
        }
        else if (x == 3)
        {
            a[4][i]++;
            a[5][i]++;
        }
        else if (x == 4)
        {
            a[9][i]++;
            a[10][i]++;
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 12; j++)
            hh[j][i] = hh[j][i - 1] + a[j][i];  //求前缀和

    scanf("%d%d%d", &p, &q, &m);
    if (p > q) swap(p, q);
    for (int i = 1; i <= m; i++)
    {
        int u, v, ans;
        scanf("%d%d%d", &month, &u, &v);
        if (u > v)  swap(u, v);

        if (u == p || u == q || v == p || v == q) //只要有点在桥上面时一定不走桥最优
             ans = (len(u, v)>=len(v, u)?len(u,v):len(v,u));
        else if ((u > p && u < q) && (v > p && v < q))  //两点处同一区域时一定不走桥最优
            ans = (len(u, v)>=len(v, u)?len(u,v):len(v,u));
        else if(!(u > p && u < q) && !(v > p && v < q)) //两点处同一区域一定不走桥最优
            ans = (len(u, v)>=len(v, u)?len(u,v):len(v,u));
        else if (u > p && u < q)  //u,v在桥两边且u > p && u < q(情况二)
            {
                ans = len(u,v);
                if(len(v, u) > ans) ans = len(v, u);
                if((len(q, v) + len(p, u)) > ans) ans = len(q, v) + len(p, u);
                if((len(u, q) + len(v, p)) > ans) ans = len(u, q) + len(v, p);
            }
        else if (v > p && v < q)  //u,v在桥两边且v > p && v < q(情况一)
            {
                ans = len(u,v);
                if((len(v, u)) > ans) ans = len(v, u);
                if((len(u, p) + len(v, q)) > ans) ans = len(u, p) + len(v, q);
                if((len(q, u) + len(p, v)) > ans) ans = len(q, u) + len(p, v);
            }
        if (ans)
            printf("%d\n", ans);
        else
            printf("So Sad.\n");
    }
}

int main()
{
    while (scanf("%d", &n) == 1)  //n为0的时候结束,否则可以一直读
    {
        solve();
    }
    return 0;
}

输入数据:
10
1 1 2 4 3 2 4 4 3 3
3 9
5
1 1 5
1 3 9
3 5 10
7 1 10
10 2 9
输出数据:
2
2
4
So Sad.
3



活动打卡代码 AcWing 4405. 统计子矩阵

温柚子
2个月前

第十二届蓝桥杯c++B组第一场第六题

考试求稳就直接推出公式用暴力了

方法一:前缀和 + 暴力四重枚举(500 ^ 4 = 6.25 * 10 ^ 10 会超时,估计会过70%的数据)

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 510;

LL k,res;
int n,m,x1,y1,x2,y2;
int a[N][N],s[N][N];

int main()
{
    cin>>n>>m>>k;
    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] + a[i][j] - s[i-1][j-1];

    for(int x1 = 1;x1 <= n;x1++)
     for(int y1 = 1;y1 <= m;y1++)
      for(int x2 = x1;x2 <= n;x2++)
       for(int y2 = y1;y2 <= m;y2++)

        {
            LL t = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1];
            if(t <= k) res++;
        }
        cout<<res;
        return 0;
}

方法二:前缀和+双指针(将四重循环优化为三重循环,500 ^ 3 = 1.25 * 10 ^ 8,可以AC)

待更新


活动打卡代码 AcWing 4403. 修剪灌木

温柚子
2个月前

第十三届蓝桥杯c++B组第一场第四题

本题为规律题,将3456个灌木高度的情况枚举出来,就会发现是一个从前半段第一个数2 * n - 2 开始依次递减2,后半段翻转前半段的对称数组~~

如果不会翻转数组的看过来,两次模拟前半段和后半段就ok啦

#include<iostream>

using namespace std;

const int N = 10010;

int n;
int a[N];

int main()
{
    cin>>n;
    a[1] = 2 * n - 2;
    for(int i = 2;i <= (n + 1) / 2;i++) a[i] = a[i-1] - 2;
    if(n % 2)
    {
        for(int i = (n + 1) / 2 + 1;i<=n;i++) a[i] = a[i-1] + 2;
        for(int i = 1;i <= n;i++) cout<<a[i]<<endl;
        return 0;
    }
    else
    {
        a[n / 2 + 1] = a[(n + 1) / 2];
        for(int i = n / 2 + 2;i <= n;i++) a[i] = a[i-1] + 2;
        for(int i = 1;i <= n;i++) cout<<a[i]<<endl;
        return 0;
    }
    return 0;
}


活动打卡代码 AcWing 4402. 刷题统计

温柚子
2个月前

第十三届蓝桥杯c++B组第一场第三题

暴力枚举,通过取模代替while循环防止超时

#include<iostream>
#include <cstring>
#include <algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

LL a,b,n,res;

int main()
{
    cin>>a>>b>>n;
    LL t = a * 5 + b * 2;
    res = n / t * 7;
    n %= t;

    for(int i = 0;i<5;i++)
    {
        if(n >= a)
        {
            n -= a;
            res++;
        }
        if(n != 0 && n < a)
        {
            cout<<res+1;
            return 0;
        }
        if(n == 0)
        {
            cout<<res;
            return 0;
        }
    }

    for(int i = 0;i<2;i++)
    {
        if(n >= b)
        {
            n -= b;
            res++;
        }
        if(n != 0 && n < b)
        {
            cout<<res+1;
            return 0;
        }
        if(n == 0)
        {
            cout<<res;
            return 0;
        }
    }
    return 0;
}



温柚子
2个月前

现在是蓝桥杯4.9当天0:17,可能是我参加蓝桥杯之前的最后一次打卡了,许愿稳定发挥省一吧

此题为y总考前押的题

祝各位看到的小伙伴旗开得胜嗷~~~

#include<iostream>

using namespace std;

int w,x1,x2,x3,x4,x5,x6,x7;
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool is_vaild(int yy,int mm,int dd)
{
    if(mm < 1 || mm > 12 || dd < 1) return false;
    if(mm != 2)
    {
        if(dd > days[mm]) return false;
    }
    else
    {
        int leap = ((yy % 4 == 0 && yy % 100 != 0) || yy % 400 == 0);
        if(dd > 28 + leap) return false;
    }
    return true;
}

int main()
{
    int n;
    cin>>n;
    for(int i = 19000101;i<=((1900 + n - 1) * 10000 + 1231);i++)
    {
        int year = i / 10000,month = i % 10000 / 100,day = i % 100;
        if(is_vaild(year,month,day))
        {
            w = (w + 1) % 7;
            if(day == 13)
            {
                if(w == 6) x1++;
                else if(w == 0) x2++;
                else if(w == 1) x3++;
                else if(w == 2) x4++;
                else if(w == 3) x5++;
                else if(w == 4) x6++;
                else x7++;
            }
        }
    }
    cout<<x1<<' '<<x2<<' '<<x3<<' '<<x4<<' '<<x5<<' '<<x6<<' '<<x7;
    return 0;
}


分享 数圈圈

温柚子
2个月前

进制转换问题(十进制转为十六进制)

#include<iostream>

using namespace std;

long long n,x;
string s;
char c;
int res;

int main()
{
    cin>>n;

    if(n == 0)
    {
        cout<<1<<endl;
        return 0;
    }
    else
  {
    while(n)
    {
        x = n % 16;
        if(x < 10) c = x + '0';
        else c = x + 'A' - 10;
        s += c;
        n /= 16;
    }

    for(int i = 0;s[i];i++)
    {
        if(s[i]=='0' || s[i] == '4' || s[i] == '6' || s[i] == '9' || s[i] == 'A' || s[i] == 'D') res++;
        else if(s[i] == '8' || s[i] == 'B') res += 2;
        else continue;
    }

    cout<<res;
  }
    return 0;
}


分享 包子凑数

温柚子
2个月前

第八届蓝桥杯c++B组第八题

dp思想

#include<iostream>

using namespace std;

const int N = 100010;

int n,d,res;
int w[N],f[N];

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>w[i];
    int d = w[1];
    for(int i = 2;i<=n;i++) d = gcd(d,w[i]);
    if(d != 1)
    {
        cout<<"INF";
        return 0;
    }
    else
    {
        f[0] = 1;
        for(int i = 1;i<=n;i++)
         for(int j = w[i];j<=N;j++)
          if(j >= w[i]) f[j] = max(f[j],f[j - w[i]]);

        for(int i = 1;i<=N;i++)
        {
            if(!f[i]) res++;
        }
        cout<<res;
        return 0;
    }
    return 0;
}



温柚子
2个月前

蓝桥杯模拟赛

复习蛇形矩阵的构造
方法一:

#include<iostream>
#include<cstring>

using namespace std;

int n,m;
int f[40][40];

int main()
{
    cin>>n>>m;
    int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};

    for(int d = 0,k = 1,x = 0,y = 0;k <= m * n;k++)
    {
        f[x][y] = k;
        int a = x + dx[d],b = y + dy[d];
        if(a<0||a>n-1||b<0||b>m-1||f[a][b])
        {
            d = (d + 1) % 4;
            a = x + dx[d],b = y + dy[d];
        }
        x = a,y = b;
    }

    cout<<f[19][19];
    return 0;
}

方法二:

#include<iostream>

using namespace std;

int a[40][40];

int main() {
    int t=0, x=1, y=1;
    t = a[x][y] = 1;
    while (t < 30 * 30) {
        while (y + 1 <= 30 && !a[x][y + 1]) a[x][++y] = ++t;
        while (x + 1 <= 30 && !a[x + 1][y]) a[++x][y] = ++t;
        while (y - 1 > 0 && !a[x][y - 1]) a[x][--y] = ++t;
        while (x - 1 > 0 && !a[x - 1][y]) a[--x][y] = ++t;

    }
    cout << a[20][20];
    return 0;
}


分享 砝码称重

温柚子
2个月前

第十二届蓝桥杯c++B组第一场第七题

方法一:dfs(可过5/10个数据)

#include<iostream>

using namespace std;

const int N = 100010;

int n,sum,res;
int a[N],w[N];

void dfs(int u,int ans)
{
    if(u > n)
    {
        if(ans <= 0) return ;
        else
        {
            a[ans]++;
            return ;
        }
    }
    dfs(u+1,ans);
    dfs(u+1,ans + w[u]);
    dfs(u+1,ans - w[u]);
}

int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>w[i],sum += w[i];
    dfs(1,0);
    for(int i = 1;i<=sum;i++)
    {
        if(a[i] > 0) res++;
    }
    cout<<res;
    return 0;
}

方法二:dp

#include<iostream>

using namespace std;

const int N = 110,M = 200010,B = M / 2;

int n,m;
int w[N];
bool f[N][M];

int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>w[i],m += w[i];
    f[0][B] = true;

    for(int i = 1;i<=n;i++)
     for(int j = -m;j<=m;j++)
      {
          f[i][j + B] = f[i-1][j + B];
          if(j - w[i] >= -m) f[i][j + B] |= f[i-1][j - w[i] + B];
          if(j + w[i] <= m) f[i][j + B] |= f[i-1][j + w[i] + B];
      }

      int res = 0;
      for(int j = 1;j<=m;j++)
      {
          if(f[n][j+B]) res++;
      }
      cout<<res;
      return 0;
}


分享 货物摆放

温柚子
2个月前

第十二届蓝桥杯c++B组第一场第四题

#include<iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

int cnt0,cnt1,cnt2;
LL n;

int main()
{
    cin>>n;
    for(LL i = 1;i * i * i <= n;i++)
    {
         if(n % i) continue;  //减少无用的循环次数
     for(LL j = i;i * j * j <= n;j++)
     {
         if(n % j) continue;  //减少无用的循环次数
         LL k = n / (i * j);
         if(i * j * k == n)
         {
             cnt0++;
             if(i == j && j == k) cnt2++;
             else if (i == j || j == k || i == k) cnt1++;
         }
     }

    }
     cout<<cnt0 * 6 - cnt1 * 3 - cnt2 * 5;
     return 0;
}