您现在的位置是:首页 > 学习心得 > 程序人生程序人生

数据结构与算法上机

卞振伟2019-05-03【程序人生】人已围观

简介查重很严,严禁抄袭。仅供借鉴学习。
欢迎留言讨论问题
第五周第三题,题目是无向图,但是代码写成了有向图
修改前 G[x][y] = (1< 修改后 G[x][y] = G[y][x] = (1< 感谢指正

第一周
#include<bits/stdc++.h>
#include<sstream>

using namespace std;

#define maxn 1010
vector<int> a;
set<int> b;

int main(){
    string s;
    getline(cin,s);
    stringstream stream(s);
    int val;
    while(stream >> val){
        a.push_back(val);
        b.insert(val);
    }
    int len = a.size();
    for(auto it = b.begin(); it != b.end(); ++it){
        if(count(a.begin(), a.end(), *it) > len/2){
            cout<<*it;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}
#include<bits/stdc++.h>
#include<sstream>

using namespace std;
vector< pair<int,int> > a;

void solve(int n){
    int i, j, sum;
    for(i = 1; i < n; ++i){
        sum = 0;
        for(j = i; sum < n; ++j){
            sum += j;
        }
        if(sum == n)
            a.push_back(make_pair(i, j-1));
    }
}

int main(){
    int n;
    cin >> n;
    solve(n);
    if(a.size()==0){
        cout << "NONE";
    }
    else{
        for(auto it = a.begin(); it != a.end(); ++it){

            for(int i = (*it).first; i <= (*it).second; ++i){
                cout << i;
                if(i != (*it).second)
                    cout << " ";
            }
            if(it != a.end())
                cout << endl;
        }
    }
    return 0;
}
#include<bits/stdc++.h>

using namespace std;
int a[10];
int days[12]={31,28,31,30,31,30,31,31,30,31,30,31};

bool isLeapYear(int n){
    if(n%400 == 0 || (n%4 == 0 && n%100 != 0)){
        return true;
    }
    return false;
}

void solve(int n){
    int year = 1900;
    int day = 13;
    a[13%7] ++;
    for(int i = 0; i < n; ++i){
        if(isLeapYear(1900 + i)){
            for(int j = 0; j < 12; ++j){
                if(j == 1)  day += days[j] + 1;
                else        day += days[j];
                a[day%7] ++;
            }
        }
        else{
            for(int j = 0; j < 12; ++j){
                day += days[j];
                a[day%7] ++;
//                cout << " ***** " << j+1 << " " << day % 7 << endl;
            }
        }
    }
    a[day%7] --;
}

int main(){
    int n;
    cin >> n;
    solve(n);
    cout<<a[6];
    for(int i = 0; i < 6; ++i){
        cout << " ";
        cout << a[i];
    }
    return 0;
}
第二周
#include<bits/stdc++.h>

using namespace std;

bool isRun(int year){
    if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0 ))
        return true;
    return false;
}

int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main(){
    int y,m,d;
    while(cin>>y>>m>>d){
        int res = 0;
        if(isRun(y)){
            for(int i = 0; i < m-1; ++i){
                res += days[i];
            }
            res += d;
            if(m > 2)
                res += 1;
        }
        else{
            for(int i = 0; i < m-1; ++i){
                res += days[i];
            }
            res += d;
        }
        cout<<res<<endl;
    }
    return 0;
}
#include<bits/stdc++.h>

using namespace std;

int main(){
    string s;
    cin>>s;
    int a[10];
    for(int i = 0; i < s.size(); ++i)
        a[i] = i;
    do{
        for(int i = 0; i < s.size(); ++i){
            cout<<s[a[i]];
        }
        cout<<endl;
    }while(next_permutation(a, a+s.size()));
    return 0;
}
#include<stdio.h>
#include<string.h>

int G[1010][1010];
int vst[1010];
int n;

void dfs(int x){
    int i;
    for(i = 0; i < n; ++i){
        if(!vst[i] && G[x][i]){
            vst[i] = 1;
            dfs(i);
        }
    }
}

int main(){
    memset(vst, 0, sizeof(vst));
    scanf("%d", &n);
    int i, j;
    for(i = 0; i < n; ++i)
        for(j = 0; j < n; ++j)
            scanf("%d", &G[i][j]);
    int ans = 0;
    for(i = 0; i < n; ++i){
        if(!vst[i]){
            ans++;
            vst[i] = 1;
            dfs(i);
        }
    }
    printf("%d", ans);
    return 0;
}
第三周
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4+10;
int n, m;
int par[maxn];
int v[maxn];

int Find(int x){
    if(par[x] == x)
        return x;
    return par[x] = Find(par[x]);
}

void init(){
    for(int i = 0; i <= n; ++i)
        par[i] = i;
}

void Union(int x, int y){
    par[Find(x)] = Find(y);
}

int main(){
    while(~scanf("%d%d", &n, &m)){
        init();
        memset(v, 0, sizeof(v));
        for(int i = 0; i < m; ++i){
            int x, y;
            scanf("%d%d", &x, &y);
            Union(x, y);
            v[x]++;
            v[y]++;
        }
        int res = Find(1);
        for(int i = 2; i <= n; ++i){
            if(res != Find(i)){
                printf("0\n");
                return 0;
            }
        }
        for(int i = 1; i <= n; ++i)
            if(v[i]&1){
                printf("0\n");
                return 0;
            }
        printf("1\n");
    }
    return 0;
}
二  这里用多种方式解
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;

int n;
int x[maxn], y[maxn];
int m[maxn];
double G[maxn][maxn];
int vst[maxn];
double d[maxn];

void spfa(int s){
   queue<int> q;
   q.push(s);
   for(int i = 0; i < n; ++i){
       vst[i] = 0;
       d[i] = inf;
   }
   vst[s] = 1;
   d[s] = 0;
   while(!q.empty()){
        int k = q.front();
        q.pop();
        vst[k] = 0;
        for(int j = 0; j < n; ++j){
            if( d[j] > max(d[k], G[k][j]) ){
                d[j] = max(d[k], G[k][j]);
                if(vst[j] == 0){
                    vst[j] = 1;
                    q.push(j);
                }
            }
        }
   }
}

int main(){
    scanf("%d", &n);
    int sum = 0;
    for(int i = 0; i < n; ++i){
        scanf("%d%d%d",&x[i],&y[i],&m[i]);
        sum += m[i];
    }
    for(int i = 0; i < n; ++i){
        for(int j = i+1; j < n; ++j){
            G[i][j] = G[j][i] = sqrt( (double)(x[i]-x[j]) * (double)(x[i]-x[j]) + 
                                      (double)(y[i]-y[j]) * (double)(y[i]-y[j]) );
        }
    }
    spfa(0);
    double ans = 0;
    for(int i = 0; i < n; ++i)
        ans += d[i] * m[i];
    printf("%.2f\n", ans / sum);
    return 0;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;

int n;
int x[maxn], y[maxn];
int m[maxn];
double G[maxn][maxn];
double d[maxn];
int vst[maxn];

void Dijkstra(int s){
    for(int i = 0; i <= n; ++i){
        vst[i] = 0;
        d[i] = inf;
    } 
    vst[s] = 1;
    d[s] = 0;
    for(int i = 0; i < n-1; ++i){
        int Min = inf;
        int k = s;
        for(int j = 0; j < n; ++j){
            if(!vst[j] &&  Min > d[j]){
                Min = d[j];
                k = j;
            }
        }
        vst[k] = 1;
        for(int j = 0; j < n; ++j){
            if(G[k][j])
                d[j] = min(d[j],  max(d[k], G[k][j]) );
        }
    }
}

int main(){
    scanf("%d", &n);
    int sum = 0;
    for(int i = 0; i < n; ++i){
        scanf("%d%d%d",&x[i],&y[i],&m[i]);
        sum += m[i];
    }
    for(int i = 0; i < n; ++i){
        for(int j = i+1; j < n; ++j){
            G[i][j] = G[j][i] = sqrt( (double)(x[i]-x[j]) * (double)(x[i]-x[j]) + 
                                      (double)(y[i]-y[j]) * (double)(y[i]-y[j]) );
        }
    }
    Dijkstra(0);
    double ans = 0;
    for(int i = 0; i < n; ++i)
        ans += d[i] * m[i];
    printf("%.2f\n", ans / sum);
    return 0;
}
#include<cstdio>
#include<string.h>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn = 1010;

double G[maxn][maxn];
int x[maxn];
int y[maxn];
int m[maxn];
int n;
void Floyd(){
    for(int k = 0; k < n; ++k){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                G[i][j] = min(G[i][j], max(G[i][k], G[k][j]));
            }
        }
    }
}

int main(){
    scanf("%d", &n);
    int sum = 0;
    for(int i = 0; i < n; ++i){
        scanf("%d%d%d", &x[i], &y[i], &m[i]);
        sum += m[i];
    }
    for(int i = 0; i < n; ++i){
        for(int j = i+1; j < n; ++j){
            G[i][j] = G[j][i] = sqrt((double)(x[i]-x[j]) * (double)(x[i]-x[j]) + (double)(y[i]-y[j]) * (double)(y[i]-y[j]) );
        }
    }
    Floyd();
    double ans = 0;
    for(int i = 0; i < n; ++i)
        ans += G[0][i] * m[i];
    printf("%.2f\n", ans / sum);
    return 0;
}
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e2+10;
int n;
int a[maxn];
typedef struct Tree{
    int x;
    struct Tree *l, *r;
    Tree(){
        l = r = NULL;
    }
    Tree(int v){
        l = r = NULL;
        x = v;
    }
}*PTree;

void bulid(int x, PTree p, int pre){
    if(x < p->x){
        if(p->l == NULL){
            p->l = new Tree(x);
            printf("%d\n", p->x);
        }
        else
            bulid(x, p->l, p->x);
    }
    else{
        if(p->r == NULL){
            p->r = new Tree(x);
            printf("%d\n", p->x);
        }
        else
            bulid(x, p->r, p->x);
    }
}

int main(){
    while(~scanf("%d", &n)){
        PTree T = new Tree();
        for(int i = 0; i < n; ++i){
            scanf("%d", &a[i]);
            if(!i){
                T->x = a[i];
                printf("-1\n");
            }
            else{
                bulid(a[i], T, -1);
            }
        }
        delete T;
    }
    return 0;
}
第四周
#include <bits/stdc++.h>

using namespace std;

int n;
queue<int> q;
stack<int> s;

int main(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        int x;
        cin >> x;
        q.push(x);
    }
    while(!q.empty()){
        s.push(q.front());
        q.pop();
    }
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
}
#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> ans;

int main(){
    cin >> n >> k;
    if(n < 0){
        n = -n;
        cout<<"-";
    }
    while(n){
        ans.push_back(n%k);
        n /= k;
    }
    reverse(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); ++i){
        if(ans[i] > 9)
            cout<<char(ans[i]-10+'a');
        else
            cout<<ans[i];
    }
}
#include <bits/stdc++.h>

using namespace std;

int n, m;
const int maxn = 1e3+10;

struct Point{
    int x, y;
    Point(int xx, int yy):x(xx),y(yy){}
    Point(){}
};

struct Win{
    Point s, e;
    int pos;
    Win(Point ss, Point ee, int p):s(ss),e(ee),pos(p){}
    Win(){}
};

Win win[maxn];
int Hash[maxn];

bool check(int x, int y, Win a){
    if(x < a.s.x || x > a.e.x || y < a.s.y || y > a.e.y)
        return false;
    return true;
}

int main(){
    while(~scanf("%d %d", &n, &m)){
        for(int i = 0; i < n; ++i){
            Point a, b;
            scanf("%d%d%d%d", &a.x, &a.y, &b.x, &b.y);
            win[i] = Win(a, b, i+1);
            Hash[i] = i;
        }
        int k = n-1;
        for(int i = 0; i < m; ++i){
            int x, y;
            scanf("%d%d", &x, &y);
            for(int j = k; j >= 0; --j){
                if( Hash[j] != -1 && check(x, y, win[Hash[j]])){
                    Hash[++k] = Hash[j];
                    printf("%d\n", win[Hash[j]].pos);
                    Hash[j] = -1;
                    break;
                }
                if(!j)
                    printf("IGNORED\n");
            }
        }
    }
    return 0;
}
第五周
#include<bits/stdc++.h>

using namespace std;

int n;
vector<int> v;

int main(){
    while(~scanf("%d", &n)){
        if(!n)
            return 0;
        v.clear();
        int x;
        for(int i = 0; i < n; ++i){
            scanf("%d", &x);
            v.push_back(x);
        }
        sort(v.begin(), v.end());
        if(v.size()&1)
            printf("%d\n", v[v.size()/2]);
        else{
            printf("%d\n", (v[v.size()/2] + v[v.size()/2-1])/2);
        }
    }
    return 0;
}
#include<bits/stdc++.h>
#include<sstream>
using namespace std;

int n, x;
vector<int> a, b;

void solve(){
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    reverse(a.begin(),a.end()); 
    for(int i = 0; i < a.size(); ++i)
        printf("%d ", a[i]);
    for(int i = 0; i < b.size(); ++i)
        printf("%d ", b[i]);
}

int main(){
    string s;
    getline(cin, s);
    stringstream ss(s);
    while(ss>>x){
        if(x&1)
            a.push_back(x);
        else
            b.push_back(x);
        if(a.size()+b.size() == 10){
            solve();
            a.clear();
            b.clear();
        }
    }
    return 0;
}

这里附三种解法
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int n, m;
int G[maxn][maxn];
int d[maxn];
int vst[maxn];

void spfa(int s){
    queue<int> q;
    for(int i = 0; i <= n; ++i){
        d[i] = inf;
        vst[i] = 0;
    }
    d[s] = 0;
    vst[s] = 1;
    q.push(s);
    while(!q.empty()){
        int k = q.front();
        vst[k] = 0;
        q.pop();
        for(int j = 0; j < n; ++j){
            if(G[k][j])
                if(d[j] > d[k]+G[k][j]){
                    d[j] = d[k] + G[k][j];
                    if(!vst[j]){
                        vst[j] = 1;
                        q.push(j);
                    }
                }
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    memset(G, 0, sizeof(G));
    for(int i = 0; i < m; ++i){
        int x, y;
        scanf("%d %d", &x, &y);
        G[x][y] = G[y][x] = (1<<i);
    }
    spfa(0);
    for(int i = 1; i < n; ++i)
        printf("%d\n", d[i] == inf ? -1 : d[i]);
    return 0;
}
#include<cstdio>

using namespace std;

const int maxn = 110;
const int inf = 0x3f3f3f3;
int n, m;
int G[maxn][maxn];
int d[maxn];
int vst[maxn];

void Dijkstra(int s){
    for(int i = 1; i <= n; ++i){
        d[i] = inf;
        vst[i] = 0;
    }
    d[s] = 0;
    vst[s] = 1;
    for(int i = 0; i < n-1; ++i){
        int Min = inf;
        int k = s;
        for(int j = 1; j <= n; ++j){
            if(!vst[j] && Min > d[j]){
                Min = d[j];
                k = j;
            }
        }
        vst[k] = 1;
        for(int j = 1; j <= n; ++j){
            if(G[k][j])
            if(!vst[j] && d[j] > d[k] + G[k][j])
                d[j] = d[k] + G[k][j];
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i){
        int x, y;
        scanf("%d %d", &x, &y);
        G[x][y] = G[y][x] = (1<<i);
    }
    Dijkstra(0);
    for(int i = 1; i < n; ++i)
        printf("%d\n", d[i] == inf ? -1 : d[i]);
    return 0;
}
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 110;
const int inf = 0x3f3f3f3;
int n, m;
int G[maxn][maxn];
int d[maxn];
int vst[maxn];

void Floyd(){
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= m; ++j)
            G[i][j] = inf;
    for(int i = 0; i < m; ++i){
        int x, y;
        scanf("%d %d", &x, &y);
        G[x][y] = G[y][x] = (1<<i);
    }
    Floyd();
    for(int i = 1; i < n; ++i)
        printf("%d\n", G[0][i] == inf ? -1 : G[0][i]);
    return 0;
}
第六周
#include<bits/stdc++.h>

using namespace std;

int main(){
    int a, n;
    cin >> a >> n;
    int ans = 0;
    int tmp = a;
    for(int i = 0; i < n; ++i){
        ans += a;
        a *= 10;
        a += tmp;
    }
    cout<<ans;
    return 0;
}
#include<bits/stdc++.h>

using namespace std;

const int maxn = 110;
int a[maxn], b[maxn];

int main(){
    int n, val;
    stack<int> s;
    cin >> n;
    int k = 0;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    s.push(a[k++]);
    for(int i = 0; i < n; ++i){
        cin >> val;
        if(s.size()!=0 && s.top() == val){
            s.pop();
            continue;
        }
        while(k < n){
            s.push(a[k++]);
            if(s.top() == val){
                 s.pop();
                break;
            }
        }
    }
    if(s.size())
        cout<<0;
    else
        cout<<n;
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 30;
int x[maxn], y[maxn];
int n, m;
int main(){
    cin >> n;
    while(n--){
        cin >> m;
        for(int i = 0; i < m; i++)
            cin >> x[i] >> y[i];
        sort(x, x+m);
        sort(y, y+m);
        int m_x = x[m/2], m_y = y[m/2];
        int sum = 0;
        for(int i = 0; i < m; ++i)
            sum += abs(x[i]-m_x) + abs(y[i]-m_y);
        cout << sum << endl;
    }
    return 0;
}
第七周
#include<bits/stdc++.h>

using namespace std;

int a[100];

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    sort(a, a+n);
    printf("%d", a[n-m]);
    return 0;
}
#include<bits/stdc++.h>

using namespace std;
long a;
char n[100];
long b;
char res[100];
void conversion(char s[],char s2[],long d1,long d2){
    long i,j,t,num;
    char c;
    num=0;
    for (i=0; s[i]!='\0'; i++){
        if (s[i]<='9'&&s[i]>='0')
            t=s[i]-'0';
        else{
            s[i] = toupper(s[i]);
            t = s[i]-'A'+10;
        }
        num=num*d1+t;
    }
    i=0;
    while(1){
        t=num%d2;
        if (t<=9) s2[i]=t+'0';
        else s2[i]=t+'A'-10;
        num/=d2;
        if (num==0) break;
            i++;
    }
    s2[i+1]='\0';
    for(int k = i; k >= 0; --k)
        printf("%c", s2[k]);
}

int main(){
    scanf("%ld%s%ld", &a, n, &b);
    conversion(n, res, a, b);
    return 0;
}
#include<bits/stdc++.h>

using namespace std;

int a[100][100];
int n;

int main(){
    scanf("%d", &n);
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        if(i & 1)
            for(int j = i; j >= 1; --j)
                a[j][i+1-j] = ++ans;
        else
            for(int j = 1; j <= i; ++j)
                a[j][i+1-j] = ++ans;
    }
    ans = n*n;
    for(int i = 1; i <= n-1; ++i){
        if(i & 1)
            for(int j = i; j >= 1; --j)
                a[n-j+1][n-i+j] = ans--;
        else
            for(int j = 1; j <= i; ++j)
                a[n-j+1][n-i+j] = ans--;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j)
            printf("%4d", a[i][j]);
        printf("\n");
    }
    return 0;
}
第八周
#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, x;
    scanf("%d", &n);
    int sum = 0;
    while(n--){
        scanf("%d", &x);
        if(x < 45)
            sum ++;
    }
    printf("%d", sum*400);
    return 0;
}
#include<bits/stdc++.h>

using namespace std;

int a[110][110];
int dp[110][110];

int main(){
    int n, x;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= i; ++j)
            scanf("%d", &a[i][j]);
    }
    for(int i = 1; i <= n; ++i)
        dp[n][i] = a[n][i];
    for(int i = n-1; i >= 1; --i){
        for(int j = 1; j <= i; ++j)
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j];
    }
    printf("%d", dp[1][1]);
    return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int t, n, m;
int G[maxn][maxn];
int vst[maxn];
int d[maxn];

void Dijkstra(int s){
    for(int i = 0; i <= n; ++i){
        d[i] = 0;
        vst[i] = 0;
    }
    d[s] = inf;
    vst[s] = 1;
    for(int i = 0; i < n-1; ++i){
        int Max = 0;
        int k = s;
        for(int j = 1; j <= n; ++j){
            if(!vst[j] && Max < d[j]){
                Max = d[j];
                k = j;
            }
        }
        vst[k] = 1;
        for(int j = 1; j <= n; ++j){
            if(G[k][j]){
                d[j] = max(d[j], min(d[k], G[k][j]));
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0;i < m; ++i){
        int x, y, v;
        scanf("%d%d%d",&x,&y,&v);
        if(G[x][y] == 0 || (G[x][y] && G[x][y] < v  ))
            G[x][y] = G[y][x] = v;
    }
    Dijkstra(1);
    printf("%d", d[n]);
    return 0;
}
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+10;
int n, m, x;
int ans[maxn];
map<int,int> mp;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i){
        scanf("%d", &x);
        mp[x] ++;
        ans[i] = mp[x];
    }
    for(int i = 0; i < m; ++i){
        scanf("%d", &x);
        printf("%d\n", ans[x-1]);
    }
    return 0;
}

Tags:

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00