头像

王子毓




离线:14天前


最近来访(25)
用户头像
Icy-Laurel
用户头像
fwyize
用户头像
垫底抽風
用户头像
卿故倾.
用户头像
Noir
用户头像
然予
用户头像
caoxiaobeiupupup
用户头像
Sheldon__
用户头像
.凌桓
用户头像
我去2001年
用户头像
rsy
用户头像
会飞的泡泡
用户头像
majoege
用户头像
Mejiofranky
用户头像
Moyou
用户头像
不拿NOI金牌不改名
用户头像
荒途孤影

活动打卡代码 AcWing 1726. 挤奶顺序

王子毓
19天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m, k;
int q[N];
int p[N];
bool st[N];

int main()
{
    cin >> n >> m >> k;

    bool flag = false;
    for (int i = 1; i <= m; i ++ )
    {
        cin >> q[i];
        if (q[i] == 1) flag = true;
    }

    memset(p, -1, sizeof p);
    for (int i = 0; i < k; i ++ )
    {
        int a, b;
        cin >> a >> b;
        if (a == 1)
        {
            cout << b << endl;
            return 0;
        }
        p[a] = b;
        st[b] = true;
    }

    if (flag)
    {
        for (int i = 1, j = 1; i <= m; i ++ )
        {
            while (st[j]) j ++ ;
            if (p[q[i]] != -1) j = p[q[i]];
            else
            {
                if (q[i] == 1)
                {
                    cout << j << endl;
                    return 0;
                }
                st[j] = true;
                j ++ ;
            }
        }
    }
    else
    {
        for (int i = m, j = n; i; i -- )
        {
            while (st[j]) j -- ;
            if (p[q[i]] != -1) j = p[q[i]];
            else
            {
                st[j] = true;
                j -- ;
            }
        }

        for (int i = 1; i <= n; i ++ )
            if (!st[i])
            {
                cout << i << endl;
                return 0;
            }
    }

    return 0;
}



活动打卡代码 AcWing 3347. 菊花链

王子毓
19天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int p[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> p[i];

    int res = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = i, s = 0; j < n; j ++ )
        {
            s += p[j];
            int cnt = j - i + 1;
            if (s % cnt == 0)
            {
                for (int k = i; k <= j; k ++ )
                    if (p[k] == s / cnt)
                    {
                        res ++ ;
                        break;
                    }
            }
        }

    cout << res << endl;
    return 0;
}


分享 错题分析

王子毓
19天前

错题报告

得分情况

T1:100/100

T2:100/100

T3:100/100

T4:0/100

T5:100/100

T6:0/100

T4

正确代码:

#include <iostream>
#include <algorithm>
using namespace std;
#define N 50001
typedef pair < int , int > PII;
int n;
PII Q[N];
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        int w , s;
        cin >> w >> s;
        Q[i] = { w + s , w };
    }
    sort(Q + 1,Q + 1 + n);
    int ans = -0x3f3f3f3f,sum = 0;
    for (int i = 1; i <= n; i++){
        int s = Q[i].first - Q[i].second;
         ans = max(ans , sum - s);
         sum += Q[i].second;
    }
    cout << ans;
    return 0;
}

分析:按重量值和强壮值从小到大排序即为最优解。

T6

正确代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,m;
int d[N],s[N],t[N];
int cnt[N];
ll ccnt[N];
bool check(int x){
    for(int i=1;i<=n;i++) ccnt[i]=cnt[i]-cnt[i-1];
    for(int i=1;i<=x;i++){
        ccnt[s[i]]-=d[i];
        ccnt[t[i]+1]+=d[i];
    }
    for(int i=1;i<=n;i++){
        ccnt[i]+=ccnt[i-1];
        if(ccnt[i]<0) return true;
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&cnt[i]);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i],&s[i],&t[i]);

    if(!check(m)){
        printf("0");
        return 0;
    }
    int l=1,r=m,ans=m+10;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) ans=min(ans,mid),r=mid-1;
        else l=mid+1;
    }
    printf("-1\n%d",ans);
    return 0;
}

分析:假设第i个位置无法满足订单要求,则后面的订单一定不满足要求,具有二段性,可以使用二分查找这个点。



活动打卡代码 AcWing 1660. 社交距离 II

王子毓
20天前
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n;
PII q[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;

    sort(q, q + n);

    int R = 1e8;
    for (int i = 1; i < n; i ++ )
        if (q[i].y != q[i - 1].y)
            R = min(R, q[i].x - q[i - 1].x);

    R -- ;

    int res = 0;
    for (int i = 0; i < n; i ++ )
        if (q[i].y)
        {
            int j = i + 1;
            while (j < n && q[j].y && q[j].x - q[j - 1].x <= R)
                j ++ ;
            res ++ ;
            i = j - 1;
        }

    cout << res << endl;
    return 0;
}


分享 错题报告

王子毓
22天前

错题报告

得分情况

T1:100/100

T2:100/100

T3:100/100

T4:0/100

T5:0/100

T1

100分

T2

100分

T3

100分

T4

正确代码:

#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
int sum[N];
int n,k;
int res[N];
int main()
{
    cin>>n>>k;
    long long ans = 0;
    res[0]=1;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        sum[i]%=k;
        ans += res[sum[i]];
        res[sum[i]]++;
    }
    cout<<ans<<endl;

    return 0;
}

简析:前缀和,每次都需要找在模k的意义下,前面前缀和与当前前缀和相等的个数。所以 sum[b]-sum[a] 时 每次需要找在模k的意义下0- b-1 与当前相等的,由于计算
的时候是从sum[1]开始的,所以sum[0]也需要先添加进去。

T5

正确代码:

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

using namespace std;
const int N = 15;
char map[N][N];
bool line[N][N],col[N][N],cell[3][3][N];
bool dfs (int x, int y) {
    if (y == 9) x++,y = 0;
    if (x == 9) {
        for (int i = 0;i < 9;i++)   cout << map[i] << endl;
        return true;
    }
    if (map[x][y] != '.')   return dfs(x,y + 1);
    for (int i = 1;i <= 9;i++) {
        if (!line[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
            map[x][y] = i + '0';
            line[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
            if (dfs(x,y + 1))   return true;
            line[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            map[x][y] = '.';
        }
    }
    return false;
}
int main () {
    for (int i = 0;i < 9;i++)  {
        cin >> map[i];
        for (int j = 0;j < 9;j++) {
            if (map[i][j] != '.') {
                int num = map[i][j] - '0';
                line[i][num] = col[j][num] = cell[i / 3][j / 3][num] = true;
            }
        }
    }
    dfs(0,0);
}

简析:line[i][num]表示第i行是否出现数字num;
col[j][num]表示第j列是否出现数字num;
cell[i][j][num]表示第i行j列小格子内是否出现数字num;
这样写可以避免繁杂的检查。dfs返回值设为bool类型可以在找到结果后快速退出

T6

正确代码:

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

using namespace std;

typedef long long LL;//防止爆掉int
const int N=1000010;

LL a[N],c[N];

int main()
{
    int n;
    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i];

    LL sum=0;
    for(int i=0;i<n;i++) sum+=a[i];

    LL ave=sum/n;//求平均值

    for(int i=n-1;i>0;i--)
    {
        c[i]=c[i+1]+ave-a[i];//求每个坐标所对应的常数c
    }

    sort(c,c+n);//对常数c排序

    LL res=0;
    for(int i=0;i<n;i++) 
       res+=abs(c[i]-c[n/2]);//求数轴上每个点到中点的距离

    printf("%lld\n",res);

    return 0;
}


分享 错题分析

王子毓
23天前

错题报告

得分情况

单选题:17.5/22.5

多选题:6/7.5

填空题:10/10

阅读题:16/32

完善题:7/28

总分:56.5/100

单选题

第7题

错答:A(n/2)

正答:B((n+1)/2)

分析:检索任一元素检索长度T=1+2+3+4+5+6+……+n=n(n+1)/2。因为概率相等,所以结果为T/n=(n+1)/2

第13题

错答:B(2.75)

正答:A(2.5)

分析:计算一下即可

多选题

第19题

错答:A(邻接矩阵)

正答:AC(邻接矩阵,邻接表)

分析:都是

第19题

错答:B(133)

正答:BD(133,199)

分析:都是

阅读题

第25题

错答:

正答:2 5 6 3 4 7 1

第26题

错答:6

正答:3 6 9 1 5 10 4 11 8 2 7

完善题

第27题第3空

错答:stack1[top1]=stack2[top2]

正答:stack2[top2]=stack[top2]

分析:写反了

第27题第4空

错答:stack2[top2]=stack[top2]

正答:stack1[top1]=stack2[top2]

分析:又写反了

第27题第5空

错答:

正答:top1-1

第28题第2空

错答:rowsum[i][0]

正答:rowsum[i][0]=0

分析:少打了=0

第28题第4空

错答:

正答:rowsum[i][j-1] + matrix[i][j]

第28题第5空

错答:

正答: rowsum[i][last]-rowsum[i][first-1]



分享 错题分析

王子毓
24天前

错题报告

得分情况

T1:100/100

T2:100/100

T3:14/100

T4:0/100

T5:100/100

T1

100分

简析:可以先打表创造一个斐波那切数列,再用二分判断这个数在不在

T2

100分

简析:先把数组排序,然后就可以将每一个数和前一个数比较,如果等于或小于前一个数,那么就要操作。对数组进行排序的好处在,我只要每一个数比它前一个数严格大一,那么在达到这个比前一个数大一的目的下,做的操作次数一定是最小的。

T3

正确代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
const double eps = 1e-8;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int n,m,hh,tt=-1,id;
char g[N][N];
bool st[N][N];
struct point{
  int x,y;  
}q[N*N];
void bfs(int x,int y)   
{
    point t;
    t.x=x,t.y=y;
    q[++tt]=t;
    st[t.x][t.y]=true;
    while(hh<=tt)
    {
        t=q[hh++];
        point cur;
        for(int i=0;i<8;i++)  
        {
            cur.x=t.x+dx[i];
            cur.y=t.y+dy[i];
            if(cur.x>=0 && cur.x<n && cur.y>=0 && cur.y<m && g[cur.x][cur.y]=='1' && !st[cur.x][cur.y])
            {
                st[cur.x][cur.y]=true;  
                q[++tt]=cur;         
            }
        }
    }
}
double get_hash()
{
    double sum=0;
    for(int i=0;i<=tt;i++)
    {
        for(int j=i+1;j<=tt;j++)
        {
            double x_2=(q[i].x-q[j].x)*(q[i].x-q[j].x);
            double y_2=(q[i].y-q[j].y)*(q[i].y-q[j].y);
            sum+=sqrt(x_2+y_2);
        }
    }
    return sum;
}
char getc(double val)
{
    static double mp[30];    
    for(int i=0;i<id;i++)
    {
        if(fabs(mp[i]-val)<eps)
        {
            return i+'a';
        }
    }
    mp[id++]=val;
    return id-1+'a';
}
int main(){
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for(int i=0;i<n;i++) cin>>g[i];

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='1')
            {
                tt=-1,hh=0;      
                bfs(i,j);
                char c=getc(get_hash());
                for(int k=0;k<=tt;k++)     
                {
                    g[q[k].x][q[k].y]=c;
                }
            }
        }
    }
    for(int i=0;i<n;i++) cout<<g[i]<<endl;
    return 0;
}

分析:

T4

正确代码:

#include<bits/stdc++.h>
using namespace std;
int A, B, C, res = 1;
struct t
{
    int a, b;
    string s;
};
int v[100000];
int mp[105][105];
int main()
{
    cin>>A>>B>>C;
    queue<t> q;
    q.push({0, 0, ""});
    mp[0][0] = 1;
    while(q.size())
    {
        auto f = q.front();
        q.pop();
        if(f.a==C||f.b==C)
        {
            cout<<f.s.size()<<endl;
            for(int i = 0; i < f.s.size(); i++)
            {
                if(f.s[i]=='1') cout<<"FILL(1)"<<endl;
                else if(f.s[i]=='2') cout<<"FILL(2)"<<endl;
                else if(f.s[i]=='3') cout<<"DROP(1)"<<endl;
                else if(f.s[i]=='4') cout<<"DROP(2)"<<endl;
                else if(f.s[i]=='5') cout<<"POUR(1,2)"<<endl;
                else if(f.s[i]=='6') cout<<"POUR(2,1)"<<endl;
            }
            return 0;
        }
        for(int i = 1; i <= 6; i++)
        {
            if(i == 1&&!mp[A][f.b])
            {
                q.push({A, f.b, f.s+'1'});
                mp[A][f.b] = 1;
            }
            else if(i == 2&&!mp[f.a][B])
            {
                q.push({f.a, B, f.s+'2'});
                mp[f.a][B] = 1;
            }
            else if(i == 3&&!mp[0][f.b])
            {
                q.push({0, f.b, f.s+'3'});
                mp[0][f.b] = 1;
            }
            else if(i == 4&&!mp[f.a][0])
            {
                q.push({f.a, 0, f.s+'4'});
                mp[f.a][0] = 1;
            }
            else if(i == 5)
            {
                if(B-f.b >= f.a&&!mp[0][f.b+f.a])
                { 
                    q.push({0, f.b+f.a,f.s+'5'});
                    mp[0][f.b+f.a] = 1;
                }
                if(B-f.b < f.a&&!mp[f.a-(B-f.b)][B]) 
                {
                    q.push({f.a-(B-f.b),B,f.s+'5'});
                    mp[f.a-(B-f.b)][B] = 1;
                }
            }
            else if(i == 6)
            {
                if(A-f.a >= f.b&&!mp[f.b+f.a][0])
                { 
                    q.push({f.b+f.a,0,f.s+'6'});
                    mp[f.b+f.a][0] = 1;
                }
                if(A-f.a < f.b&&!mp[A][f.b-(A-f.a)]) 
                {
                    q.push({A,f.b-(A-f.a),f.s+'6'});
                    mp[A][f.b-(A-f.a)] = 1;
                }
            }
        }
    }
    cout<<"impossible"<<endl;

    return 0;
}

简析:利用bfs遍历所有图中的连通块,之后把找到的字符c替换连通块中所有原来的字符。

T5

100分

简析:将两个罪犯看成点,怨气值看成边。将两个罪犯分别用并查集合并到其他罪犯中。问题在于不知道如何合并,设两个监狱为X和Y,当前的罪犯为a,b。
这里可以有两种情况,即a与X合并、b与Y合并,或者a与Y合并,b与X合并。
解决的方法是,先不做决定到底怎么放,而是用一个数组opposite记录下相对关系,如果opposite[x] = y,说明x和y不在一个集合中,当下次的边涉及到x和z时,那么z只能和x相对的y合并,就ok了



活动打卡代码 AcWing 1672. 疯狂的科学家

王子毓
24天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
string a, b;
int main(){
    cin >> n;
    cin >> a >> b;
    int res = 0;
    for (int i = 0; i < n; i ++ )
        if (a[i] != b[i]) {
            int j = i + 1;
            while (j < n && a[j] != b[j]) j ++ ;
            res ++ ;
            i = j;
        }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 4479. 最长子序列

王子毓
30天前
#include<bits/stdc++.h>
using namespace std;
int a[20];
bool flag[20];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        int j;
        cin>>j;
        flag[j]=true;
    }
    for(int i=0;i<n;i++){
        if(flag[a[i]]){
            cout<<a[i]<<" ";
        }
    }
    //freopen("T1","r","std.in")
    //freopen("T1","w","std.out")
    return 0;
}


活动打卡代码 AcWing 1443. 拍照

王子毓
30天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N], b[N];
bool st[N];
bool check(int a1){
    memset(st, 0, sizeof st);
    a[1] = a1;
    st[a1] = true;

    for (int i = 2; i <= n; i ++ ){
        a[i] = b[i - 1] - a[i - 1];
        if (a[i] < 1 || a[i] > n) return false;
        if (st[a[i]]) return false;

        st[a[i]] = true;
    }
    for (int i = 1; i <= n; i ++ )
        cout << a[i] << ' ';
    return true;
}
int main(){
    cin >> n;
    for (int i = 1; i < n; i ++ ) cin >> b[i];

    for (int i = 1; i <= n; i ++ )
        if (check(i))
            break;

    return 0;
}