头像

重生之我又得重生




离线:1天前


最近来访(23)
用户头像
你若成风_2
用户头像
mango_
用户头像
云衣醉梦
用户头像
yxc的小迷妹
用户头像
欣0613
用户头像
SYNUACM
用户头像
AcWing_czy
用户头像
ninado_dante
用户头像
hpstory
用户头像
stras
用户头像
宇宙有边
用户头像
椿湫_3
用户头像
恶魔波刚
用户头像
hncsxzx
用户头像
FJ_EYoungOneC
用户头像
摘樱桃
用户头像
我的江南有雨
用户头像
Aso
用户头像
爱算法爱生活
用户头像
WA声闹彻明

分享 scanf()==EOF

同样的形式,使用while(cin>>a)可以AC,但是使用while(scanf(“%d”,%a))就是TLE,使用while(scanf(“%d”,%a)==EOF)才能AC.

EOF

EOF,是End Of File的缩写,存在于文本文件的结尾,表示文件结束。EOF的值为-1。
在终端输入数据时,不会产生EOF。应用程序将一份已知的保留字符或序列解释为文件的结束,也就是EOF是ASCII码中的替换字符(ctrl+z)
EOF用作文件结束符,也常常用来判断函数是否成功执行,函数的失败时返还EOF.

“cin”和”scanf”

scanf的返回值是被输入函数scanf成功赋值的变量的个数 ,返回值>=0.
在循环条件中,没有scanf(……)!=EOF的判定,循环while将一直进行。
scanf(……)!=EOF可以替换成scanf(……)==1,或while(~scanf())
cin是输入流对象,>>是重载的运算符,cin>>的返回值就是cin对象
cin的使用:输入数据并按下enter后,数据送入输入缓冲区,cin检查缓冲区是否有可读取数据



活动打卡代码 AcWing 344. 观光之旅

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

using namespace std;

const int N = 110,INF = 0x3f3f3f3f;

int n,m;
int d[N][N],g[N][N];
int p[N][N];
int path[N],cnt;
int pos[N][N];

void get_path(int i,int j){
    if(pos[i][j]==0) return ;
    int k = pos[i][j];
    get_path(i,k);
    path[cnt++] = k;
    get_path(k,j);
}

int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++) g[i][i] = 0;
    while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            g[a][b] =g[b][a] = min(g[a][b],c);
    }

    memcpy(d,g,sizeof d);
    int res = INF;

    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
                if((long long)d[i][j]+g[j][k]+g[k][i]<res){
                    res = d[i][j]+g[j][k]+g[k][i];
                    cnt = 0;
                    path[cnt++] = k;
                    path[cnt++] = i;
                    get_path(i,j);
                    path[cnt++] = j;
                }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(d[i][j]>d[i][k]+d[k][j]){
                    d[i][j] = d[i][k]+d[k][j];
                    pos[i][j] = k;
                }
            }
    }
    if(res==INF) puts("No solution.");
    else {
        for(int i=0;i<cnt;i++)cout<<path[i]<<' ';
        cout<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 343. 排序

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

using namespace std;

const int N = 26;
int n,m;
int g[N][N],d[N][N];
bool st[N];

void print(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cout<<d[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;
}


void floyd(){
    memcpy(d,g,sizeof d);
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                d[i][j] |= d[i][k]&&d[k][j];
}

int check(){
    for(int i=0;i<n;i++)
        if(d[i][i])
        return 2;
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            if(!d[i][j]&&!d[j][i])
                return 0;

    return 1;
}

char get_min(){
    for(int i=0;i<n;i++)
        if(!st[i]){
            bool flag = true;
            for(int j=0;j<n;j++){
                if(!st[j]&&d[j][i]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                st[i] = true;
                return 'A'+i;
            }
        }
}

int main(){
    while(cin>>n>>m,n||m){
        memset(g,0,sizeof g);
        int type = 0,t;
        for(int i=1;i<=m;i++){
            char str[5];
            cin>>str;
            int a = str[0]-'A',b = str[2]-'A';
            if(!type){
                g[a][b] = 1;
                floyd();
                type = check();
                if(type) t = i;
            }
        }

        if(!type) puts("Sorted sequence cannot be determined.");
        else if(type==2) printf("Inconsistency found after %d relations.\n",t);
        else{
            memset(st,0,sizeof st);
            printf("Sorted sequence determined after %d relations: ",t);
            for(int i=0;i<n;i++) printf("%c",get_min());
            printf(".\n");
        }
    }
}


活动打卡代码 AcWing 1125. 牛的旅行

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

#define x first 
#define y second 
using namespace std;

typedef pair<int,int>PII;
const int N = 150;
const double INF = 1e20;

int n;
PII q[N];
char g[N][N];
double d[N][N],maxd[N];

double get_dist(PII a,PII b){
    double  dx = a.x-b.x,dy = a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>q[i].x>>q[i].y;
    for(int i=0;i<n;i++)cin>>g[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(i!=j) {
                if(g[i][j]=='1')d[i][j] = get_dist(q[i],q[j]);
                else d[i][j] = INF;
            }
        }
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(d[i][j]<INF)
                maxd[i] = max(maxd[i],d[i][j]);
    double res1 = 0;
    for(int i=0;i<n;i++) res1 = max(res1,maxd[i]);

    double res2 = INF;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            if(d[i][j]>=INF)//浮点数不一定精准
            res2 = min(res2,get_dist(q[i],q[j])+maxd[i]+maxd[j]);
        }
    printf("%.6lf\n",max(res1,res2));
    return 0;
}



活动打卡代码 AcWing 4718. 摆放棋子

#include<bits/stdc++.h>

using namespace std;

const int N = 1000010;
int n,m,res;
int st[N];

int main(){
    cin>>n>>m;
    if(n>m)swap(n,m);
    for(int i=1;i<=m;i++){
        if(!st[i]){
            res++;
            int x = i;
            bool flag = false;
            while(1){
                if(st[i]>=3)
                    break;
                while(x<=m){
                    if(!flag){
                        st[x]++;
                        flag = true;
                    }
                    else flag = false;
                    x+=n-1;
                }
                x = m-(x-m);
                while(x>=1){
                    if(!flag){
                        st[x]++;
                        flag = true;
                    }
                    else flag = false;
                    x-=n-1;
                }
                x = 1+1-x;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 4717. 环形队伍

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>

using namespace std;

const int N  =10;
char color[N] = {'0','R','O','Y','G','B','I','V'};
int cc[N];
int n;
vector<char>res;

bool dfs(int u){
    if(u==n){
        if(res[u-1]==res[0]) return false;
        else {
            for(int i=1;i<=7;i++)if(cc[i]==0)return false;
            for(int i=0;i<n;i++) cout<<res[i];
            return true;
        }
    }
    for(int i=1;i<=7;i++){
        int flag = 1;
        for(int j=u-1;j>=u-3&&j>=0;j--){
            if(res[j]==color[i])flag = 0;
        }
        if(flag){
            res.push_back(color[i]);
            cc[i]++;
            if(dfs(u+1)) return true;
            cc[i]--;
            res.pop_back();
        }
    }
    return false;
}


int main(){
    cin>>n;
    dfs(0);
    return 0;
}


活动打卡代码 AcWing 4716. 进球

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<string>


using namespace std;

int n;
unordered_map<string,int>mp;

int main(){
    cin>>n;
    int res = 0;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        mp[s]++;
        res = max(res,mp[s]);
    }
    for(auto it = mp.begin();it!=mp.end();it++){
        if(it->second==res)cout<<it->first<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 383. 观光

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

using namespace std;

const int N = 1010,M = 10010;

struct Ver{
    int id,type,dist;
    bool operator>(const Ver &W)const
    {
        return dist>W.dist;
    }
};

int n,m,S,T;
int h[N],e[M],w[M],ne[M],idx;
int dist[N][2],cnt[N][2];
bool st[N][2];


void add(int a,int b,int c){
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    dist[S][0] = 0;
    cnt[S][0] = 1;
    priority_queue<Ver,vector<Ver>,greater<Ver>>heap;
    heap.push({S,0,0});
    while(heap.size()){
        Ver t = heap.top();
        heap.pop();

        int ver = t.id,type = t.type,distance = t.dist,count = cnt[ver][type];
        if(st[ver][type])continue;
        st[ver][type] = true;
        for(int i= h[ver];~i;i=ne[i]){
            int j = e[i];
            if(dist[j][0]>distance+w[i]){
                dist[j][1] = dist[j][0],cnt[j][1] = cnt[j][0];
                heap.push({j,1,dist[j][1]});
                dist[j][0] = distance+w[i];
                cnt[j][0] = count;
                heap.push({j,0,dist[j][0]});
            }
            else if(dist[j][0]==distance+w[i])cnt[j][0]+=count;
            else if(dist[j][1]>distance+w[i]){
                dist[j][1] = distance+w[i];
                cnt[j][1] = count;
                heap.push({j,1,dist[j][1]});
            }
            else if(dist[j][1]==distance+w[i]) cnt[j][1]+=count;
        }
    }
    int res = cnt[T][0];
    if(dist[T][0]+1==dist[T][1]) res+=cnt[T][1];
    return res;
}

int main(){
    int cases;
    scanf("%d",&cases);
    while(cases--){
        scanf("%d%d",&n,&m);
        memset(h,-1,sizeof h);
        idx = 0;

        while(m--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }

        scanf("%d%d",&S,&T);
        printf("%d\n",dijkstra());
    }
    return 0;
}


活动打卡代码 AcWing 1134. 最短路计数

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

using namespace std;

const int N = 100010,M = 400010,mod = 100003;

int n,m;
int h[N],e[M],ne[M],idx;

int dist[N],cnt[N];
int q[N];


void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void bfs(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;cnt[1] = 1;
    int hh = 0,tt = 1;
    q[0] = 1;
    while(hh!=tt){
        int t = q[hh++];
        for(int i = h[t];~i;i=ne[i]){
            int j = e[i];
            if(dist[j]>dist[t]+1){
                dist[j] = dist[t]+1;
                cnt[j] = cnt[t];
                q[tt++] = j;
            }
            else  if(dist[j]==dist[t]+1){
                cnt[j] = (cnt[j]+cnt[t])%mod;
            }
        }
    }
}


int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    bfs();
    for(int i=1;i<=n;i++)printf("%d\n",cnt[i]);
    return 0;
}



活动打卡代码 AcWing 1131. 拯救大兵瑞恩

#include<cstring>
#include<iostream>
#include<algorithm>
#include<deque>
#include<set>

#define x first
#define y second

using namespace std;

typedef pair<int,int>PII;
const int N = 11,M = N*N,E = 400, P = 1<<10;

int n,m,p,k;

int h[M],e[E],ne[E],idx,w[E];
int g[N][N],key[M];
int dist[M][P];
bool st[M][P];

set<PII>edges;

void add(int a,int b,int c){
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}

void build(){
    int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            for(int u=0;u<4;u++){
                int x = i+dx[u],y = j+dy[u];
                if(!x||x>n||!y||y>m) continue;
                int a = g[i][j],b = g[x][y];
                if(edges.count({a,b})==0) add(a,b,0);

            }
        }
}

int bfs(){
    memset(dist,0x3f,sizeof dist);
    dist[1][0] = 0;
    deque<PII>q;
    q.push_back({1,0});
    while(q.size()){
        auto t = q.front();
        q.pop_front();
        if(st[t.x][t.y])continue;
        st[t.x][t.y] = true;

        if(t.x==n*m) return dist[t.x][t.y];
        if(key[t.x]){
            int state = t.y|key[t.x];
            if(dist[t.x][state]>dist[t.x][t.y]){
                dist[t.x][state] = dist[t.x][t.y];
                q.push_front({t.x,state});
            }
        }

        for(int i = h[t.x];~i;i=ne[i]){
            int j = e[i];
            if(w[i]&&!(t.y >> w[i]-1 & 1))continue;
            if(dist[j][t.y]>dist[t.x][t.y]+1){
                dist[j][t.y] = dist[t.x][t.y]+1;
                q.push_back({j,t.y});
            }
        }
    }
    return -1;
}

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

    for(int i=1,t=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            g[i][j] = t++;
    }
    memset(h,-1,sizeof h);
    while(k--){
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        int a = g[x1][y1],b = g[x2][y2];
        edges.insert({a,b}),edges.insert({b,a});
        if(c) add(a,b,c),add(b,a,c);
    }
    build();

    int s;
    cin>>s;
    while(s--){
        int x,y,id;
        cin>>x>>y>>id;
        key[g[x][y]] |= 1<<id - 1;
    }
    cout<<bfs()<<endl;
    return 0;
}