头像

有猷

姜堰四中




离线:4天前


活动打卡代码 AcWing 237. 程序自动分析

有猷
11天前
#include<iostream>
using namespace std;
#define re register
#define Re register
#define MAXN 1000005
int t,n,fa[MAXN];
struct node{
    int a,b;
    bool c;
}arr[MAXN];
int Hash(int x){
    return x % MAXN;
}
int find(int x){
    if(fa[x] == x)return x;
    return fa[x] = find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)] = find(y);
}
int main() {
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(re int i = 0;i <= MAXN - 1;i++){
            fa[i] = i;
        }
        for(Re int i = 1;i <= n;i++){
            scanf("%d%d%d",&arr[i].a,&arr[i].b,&arr[i].c);
            if(arr[i].c)merge(Hash(arr[i].a),Hash(arr[i].b));
        }
        bool ok = true;
        for(re int i = 1;i <= n;i++){
            if(!arr[i].c){
                if(find(Hash(arr[i].a)) == find(Hash(arr[i].b))){
                    ok = false;
                    break;
                }
            }
        }
        if(ok)puts("YES");
        else puts("NO");
    }
    return 0;
}


活动打卡代码 AcWing 1252. 搭配购买

有猷
15天前
#include<iostream>
using namespace std;
#define re register
#define Re register
#define MAXN 10005
int n,m,w,fa[MAXN],val[MAXN],cst[MAXN],opt[MAXN],num,nc[MAXN],nv[MAXN];
int find(int x){
    if(fa[x] == x)return x;
    return fa[x] = find(fa[x]);
}
void merge(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy){
        fa[fx] = fy;
        val[fy] += val[fx];
        cst[fy] += cst[fx];
    }
}
struct cloud{
    int c,d;
}a[MAXN];
int main() {
    scanf("%d%d%d",&n,&m,&w);
    for(Re int i = 1;i <= n;i++){
        fa[i] = i;
        scanf("%d%d",&cst[i],&val[i]);
    }
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        merge(u,v);
    }
    for(re int i = 1;i <= n;i++){
        if(fa[i] == i){
            num++;
            nc[num] = cst[i];
            nv[num] = val[i];
        }
    }
    for(re int i = 1;i <= num;i++){
        cout << nc[num] << ' ' << nv[num] << endl;
        for(re int j = w;j >= nc[i];j--){
            opt[j] = max(opt[j],opt[j - nc[i]] + nv[i]);
        }
    }
    printf("%d\n",opt[w]);
    return 0;
}


活动打卡代码 AcWing 1250. 格子游戏

有猷
19天前

新年快乐hh~~~~

#include<iostream>
using namespace std;
#define re register
#define Re register
#define MAXN 40405
int n,m;
int fa[MAXN];
int Hash(int x,int y){
    return x * n + y;
}
int find(int x){
    if(fa[x] == x)return x;
    return fa[x] = find(fa[x]);
}
void merge(int a,int b){
    int x = find(a),y = find(b);
    fa[x] = y;
}
int main() {
    scanf("%d%d",&n,&m);
    for(re int i = 1;i <= n * n + n;i++){
        fa[i] = i;
    }
    for(re int i = 1;i <= m;i++){
        int x,y,p,q;
        char c;
        scanf("%d%d %c",&x,&y,&c);
        p = x;q = y;
        if(c == 'D')x++;
        else y++;
        if(find(Hash(x,y)) == find(Hash(p,q))){
            printf("%d\n",i);
            return 0;
        }
        else merge(Hash(x,y),Hash(p,q));
    }
    puts("draw");
    return 0;
}


活动打卡代码 AcWing 367. 学校网络

有猷
1个月前
#include<iostream>
#include<cstring>
using namespace std;
#define re register
#define Re register
#define MAXN 105
#define MAXM 10005
int n,a,b;//general
int h[MAXN],e[MAXM],nxt[MAXM],idx,din[MAXN],dout[MAXN];//graph
int dfn[MAXN],low[MAXN],scc,top,stk[MAXN],id[MAXN],timestamp;//tarjan
bool instk[MAXN];
void add(int u,int v){
    e[idx] = v;nxt[idx] = h[u];h[u] = idx++;
}
void tarjan(int pos){
    dfn[pos] = low[pos] = ++timestamp;
    stk[++top] = pos;instk[pos] = true;
    for(re int i = h[pos];i != -1;i = nxt[i]){
        if(!dfn[e[i]]){
            tarjan(e[i]);
            low[pos] = min(low[pos],low[e[i]]);
        }
        else if(instk[e[i]])
            low[pos] = min(low[pos],dfn[e[i]]);
    }
    if(low[pos] == dfn[pos]){
        scc++;
        do{
            id[stk[top]] = scc;
            instk[stk[top]] = false;
            top--;
        }while(stk[top + 1] != pos);
    }
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(re int i = 1;i <= n;i++){
        int v;
        scanf("%d",&v);
        while(v){
            add(i,v);
            scanf("%d",&v);
        }
    }
    for(re int i = 1;i <= n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(re int i = 1;i <= n;i++){
        for(re int j = h[i];j != -1;j = nxt[j]){
            if(id[i] != id[e[j]]){
                din[id[e[j]]]++;
                dout[id[i]]++;
            }
        }
    }
    for(re int i = 1;i <= scc;i++){
        if(din[i] == 0)a++;
        if(dout[i] == 0)b++;
    }
    printf("%d\n",a);
    if(scc == 1)a = b = 0;
    printf("%d\n",max(a,b));
    return 0;
}


活动打卡代码 AcWing 2816. 判断子序列

有猷
1个月前
#include<iostream>
#include<cstring>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
int n,m,a[MAXN],b[MAXN];
int main() {
    scanf("%d%d",&n,&m);
    for(re int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
    }
    for(Re int i = 1;i <= m;i++){
        scanf("%d",&b[i]);
    }
    int top = 1;
    for(re int i = 1;i <= m;i++){
        if(b[i] == a[top])top++;
    }
    if(top > n)puts("Yes");
    else puts("No");
    return 0;
}



有猷
1个月前

这道题本人在考场上只开了long long(华丽丽的60pts)
思路其实还是简单的,是NOIP考场上唯一看得懂的题目
以下是思考过程:

管道不会形成回路,即不会发生污水形成环流的情况

说明该图是个DAG(有向无环图)

污水只能从这些接收口流入排水系统

可看出搜索时只需从接收口开始

要求 p 与 q 互素

还要约分(STL里有__gcd函数)


70pts

#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
#define MAXM 500005
#define ll long long
int n,m,s[MAXN];
int h[MAXN],e[MAXM],nxt[MAXM],idx;//graph
void add(int u,int v){
    e[idx] = v;nxt[idx] = h[u];h[u] = idx++;
}
struct node{
    ll fz,fm;
}arr[MAXN];
node operator+(node a,node b){
    node ans = (node){a.fz * b.fm + b.fz * a.fm,a.fm * b.fm};
    return ans;
}
void dfs(int pos){
    ll tmp = __gcd(arr[pos].fz,arr[pos].fm);
    arr[pos].fz /= tmp;arr[pos].fm /= tmp;
    if(s[pos])arr[pos].fm *= s[pos];
    tmp = __gcd(arr[pos].fz,arr[pos].fm);
    arr[pos].fz /= tmp;arr[pos].fm /= tmp;
    for(re int i = h[pos];i != -1;i = nxt[i]){
        if(s[e[i]] != 0)arr[e[i]] = arr[pos];
        else arr[e[i]] = arr[e[i]] + arr[pos];
        dfs(e[i]);
    }
}
int main() {
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(re int i = 1;i <= n;i++){
        scanf("%d",&s[i]);
        arr[i].fm = 1;
        for(re int j = 1;j <= s[i];j++){
            int v;
            scanf("%d",&v);
            add(i,v);
        }
    }
    for(re int i = 1;i <= m;i++){
        arr[i].fz = arr[i].fm = 1;
        dfs(i);
    }
    for(re int i = 1;i <= n;i++) {
        if(s[i] == 0)printf("%lld %lld\n",arr[i].fz,arr[i].fm);
    }
    return 0;
}

这道题得分占了我NOIP将近二分之一的分数~


那么,为啥WA?
主要原因:数据过大,会爆LL
使用unsigned long long会得到80分的好成绩
此处不再赘述


接下来咋办嘞?
我们发现此处:

node operator+(node a,node b){
    node ans = (node){a.fz * b.fm + b.fz * a.fm,a.fm * b.fm};
    return ans;
}

语句a.fm * b.fm最容易爆
优化:取公因数约分即可

90pts:

#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
#define MAXM 500005
#define ll unsigned long long
int n,m,s[MAXN];
int h[MAXN],e[MAXM],nxt[MAXM],idx;//graph
void add(int u,int v){
    e[idx] = v;nxt[idx] = h[u];h[u] = idx++;
}
struct node{
    ll fz,fm;
}arr[MAXN];
node operator+(node a,node b){
    ll tmp = __gcd(a.fm,b.fm);//优化在这里!!!!!!
    node ans = (node){a.fm / tmp * b.fz + b.fm / tmp * a.fz,a.fm / tmp * b.fm};
    return ans;
}
void dfs(int pos){
    ll tmp = __gcd(arr[pos].fz,arr[pos].fm);
    arr[pos].fz /= tmp;arr[pos].fm /= tmp;
    if(s[pos])arr[pos].fm *= s[pos];
    tmp = __gcd(arr[pos].fz,arr[pos].fm);
    arr[pos].fz /= tmp;arr[pos].fm /= tmp;
    for(re int i = h[pos];i != -1;i = nxt[i]){
        if(s[e[i]] != 0)arr[e[i]] = arr[pos];
        else arr[e[i]] = arr[e[i]] + arr[pos];
        dfs(e[i]);
    }
}
int main() {
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(re int i = 1;i <= n;i++){
        scanf("%d",&s[i]);
        arr[i].fm = 1;
        for(re int j = 1;j <= s[i];j++){
            int v;
            scanf("%d",&v);
            add(i,v);
        }
    }
    for(re int i = 1;i <= m;i++){
        arr[i].fz = arr[i].fm = 1;
        dfs(i);
    }
    for(re int i = 1;i <= n;i++) {
        if(s[i] == 0)printf("%llu %llu\n",arr[i].fz,arr[i].fm);
    }
    return 0;
}

然而,数据范围还是过大~

这时候有两种选择:高精or long double

无论哪种选择,gcd都是大问题。

蒟蒻经过思考(ˇˍˇ) ~

发现:
a % b == a - a / b * b
在浮点数中,只需将a,b下取整即可。
下取整用floor函数

P.S.输出时加setprecision函数,防止答案以指数形式出现

100pts

#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define MAXN 100005
#define MAXM 500005
#define ll unsigned long long
#define ld long double
int n,m,s[MAXN];
int h[MAXN],e[MAXM],nxt[MAXM],idx;//graph
void add(int u,int v){
    e[idx] = v;nxt[idx] = h[u];h[u] = idx++;
}
struct node{
    ld fz,fm;
}arr[MAXN];
ld gcd(ld a,ld b){
    if(a < b)swap(a,b);
    ld tmp = floor(a / b);
    if(a - tmp * b <= 0.01)return b;//浮点数不能判等!!
    return gcd(b,a - tmp * b);
}
node operator+(node a,node b){
    ld tmp = gcd(a.fm,b.fm);
    node ans = (node){a.fm / tmp * b.fz + b.fm / tmp * a.fz,a.fm / tmp * b.fm};
    return ans;
}
void dfs(int pos){
    ll tmp = gcd(arr[pos].fz,arr[pos].fm);
    arr[pos].fz /= tmp;arr[pos].fm /= tmp;
    if(s[pos]){
        tmp = gcd(arr[pos].fz,(ld)s[pos]);
        s[pos] /= tmp;
        arr[pos].fm *= s[pos];
    }
    for(re int i = h[pos];i != -1;i = nxt[i]){
        if(s[e[i]] != 0)arr[e[i]] = arr[pos];
        else arr[e[i]] = arr[e[i]] + arr[pos];
        dfs(e[i]);
    }
}
int main() {
    // ld a,b;
    // cin >> a >> b;
    // cout << gcd(a,b) << endl;//gcd写错来时用这里调试
    memset(h,-1,sizeof h);
    cin.tie(0);
    cin >> n >> m;
    for(re int i = 1;i <= n;i++){
        cin >> s[i];
        arr[i].fm = 1;
        for(re int j = 1;j <= s[i];j++){
            int v;
            cin >> v;
            add(i,v);
        }
    }
    for(re int i = 1;i <= m;i++){
        arr[i].fz = arr[i].fm = 1;
        dfs(i);
    }
    for(re int i = 1;i <= n;i++) {//防止输出以诸如1e6的形式出现
        if(s[i] == 0)cout << fixed << setprecision(0) << arr[i].fz << ' ' << arr[i].fm << endl;
    }
    return 0;
}

中考加氢!CSP2021加氢!NOIP2021加氢!
(氢的热值高于汽油)



活动打卡代码 AcWing 1174. 受欢迎的牛

有猷
1个月前

易错点用/////////标出。

#include<iostream>
#include<cstring>
using namespace std;
#define re register
#define Re register
#define MAXN 10005
#define MAXM 50005
int n,m;
int h[MAXN],nxt[MAXM],e[MAXM],idx;
int time_stamp,scc,lens[MAXN],dfn[MAXN],low[MAXN],id[MAXN];
int out_e[MAXN],stk[MAXN],top;
bool instk[MAXN];
void add(int u,int v){
    e[idx] = v;
    nxt[idx] = h[u];
    h[u] = idx++;
}
void tarjan(int pos){
    dfn[pos] = low[pos] = ++time_stamp;
    stk[++top] = pos;
    instk[pos] = true;
    for(re int i = h[pos];i != -1;i = nxt[i]){
        if(!dfn[e[i]]){
            tarjan(e[i]);
            low[pos] = min(low[pos],low[e[i]]);
        }
        else if(instk[e[i]]){
            low[pos] = min(low[pos],dfn[e[i]]);//////////
        }
    }
    if(low[pos] == dfn[pos]){
        scc++;
        do{
            instk[stk[top]] = false;
            id[stk[top]] = scc;
            lens[scc]++;
            top--;
        }while(stk[top + 1] != pos);//////////
    }
}
int main() {
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(Re int i = 1;i <= m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(re int i = 1;i <= n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(re int i = 1;i <= n;i++){
        for(re int j = h[i];j != -1;j = nxt[j]){
            if(id[i] != id[e[j]])out_e[id[i]]++;//////////
        }
    }
    int zero = 0,ans = 0;
    for(re int i = 1;i <= scc;i++){
        if(out_e[i] == 0)zero++,ans += lens[i];
        if(zero > 1){
            ans = 0;
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}


新鲜事 原文

有猷
2个月前
祝大家2020 NOIP RP++



有猷
3个月前

Acwing102.最佳牛围栏

请问:

  1. 为什么二分时 rgt - lft 要精确到0.00001?题目中是乘以1000再 向下取整
  2. 为什么输出rgt而不是lft?

谢谢大家!

#include<iostream>
using namespace std;
#define re register
#define Re register
#define ll long long
#define MAXN 100005
int n,f;
double a[MAXN],b[MAXN];
ll ans;
bool check(double mid){
    double Min = 0;
    for(re int i = f;i <= n;i++){
        Min = min(Min,b[i - f] - (i - f) * mid);
        if(b[i] - i * mid >= Min)return true;
    }
    return false;
}
int main() {
    scanf("%d%d",&n,&f);
    for(re int i = 1;i <= n;i++){
        scanf("%lf",&a[i]);
        b[i] = b[i - 1] + a[i];
    }
    double lft = 0,rgt = b[n],mid;
    while(rgt - lft >= 0.00001){//对应问题一
        mid = (lft + rgt) / 2;
        if(check(mid))lft = mid;
        else rgt = mid;
    }
    printf("%d\n",(int)(rgt * 1000));//对应问题二
    return 0;
}

问题二的数据:

10 10
6
4
2
10
3
8
5
9
4
1


活动打卡代码 AcWing 102. 最佳牛围栏

有猷
3个月前
#include<iostream>
using namespace std;
#define re register
#define Re register
#define ll long long
#define MAXN 100005
int n,f;
double a[MAXN],b[MAXN];
ll ans;
bool check(double mid){
    double Min = 0;
    for(re int i = f;i <= n;i++){
        Min = min(Min,b[i - f] - (i - f) * mid);
        if(b[i] - i * mid >= Min)return true;
    }
    return false;
}
int main() {
    scanf("%d%d",&n,&f);
    for(re int i = 1;i <= n;i++){
        scanf("%lf",&a[i]);
        b[i] = b[i - 1] + a[i];
    }
    double lft = 0,rgt = b[n],mid;
    while(rgt - lft >= 0.00001){
        mid = (lft + rgt) / 2;
        if(check(mid))lft = mid;
        else rgt = mid;
    }
    printf("%d\n",(int)(rgt * 1000));
    return 0;
}