zhaokuohaha / 2016summerprogramdesign Goto Github PK

View Code? Open in Web Editor NEW

0.0 2.0 0.0 0 B

程序设计实训

2016summerprogramdesign's Introduction

2016SummerProgramDesign

程序设计实训

代码直接贴在issues里面

2016summerprogramdesign's People

Contributors

Watchers

2016summerprogramdesign's Issues

4-R

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    static int N,M,S,E;
    static int graph[][];
    static int map[][];
    static boolean visited[];
    static int INF = 0x3f3f3f3f;
    static int dist[];
    static int tdist[];

    public static void dij(){
        dist = new int[N+1];
        tdist = new int[N+1];
        visited[S]=true;
        for(int i=0;i<=N;i++){
            dist[i] = graph[S][i];
            tdist[i] = map[S][i];
        }
        int k=0;
        for(int i=0;i<N;i++){
            int min = INF;
            for(int j=1;j<=N;j++){
                if(visited[j]==false&&min>dist[j]){
                    min = dist[j];
                    k = j;
                }
            }
            visited[k] = true;
            for(int j=1;j<=N;j++){
                if(visited[j]==false&&dist[k]+graph[k][j]<dist[j]){
                    dist[j] = dist[k]+graph[k][j];
                    tdist[j] = tdist[k]+map[k][j];
                }
                if(visited[j]==false&&dist[k]+graph[k][j]==dist[j]&&tdist[k]+map[k][j]>tdist[j]){
                    tdist[j] = tdist[k]+map[k][j];
                }
            }
        }
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int T;
        T = in.nextInt();
        for(int i=0;i<T;i++){
            N = in.nextInt();
            M = in.nextInt();
            S = in.nextInt();
            E = in.nextInt();
            graph = new int[N+1][N+1];
            map = new int[N+1][N+1];
            for(int j=0;j<=N;j++){
                Arrays.fill(graph[j],INF);
                Arrays.fill(map[j],INF);
            }
            visited = new boolean[N+1];
            for(int j=0;j<M;j++){
                int u = in.nextInt();
                int v = in.nextInt();
                int w = in.nextInt();
                int W = in.nextInt();
                graph[u][v] = graph[v][u] = w;
                map[u][v] = map[v][u] = W;
            }
            dij();
            System.out.println(dist[E]+" "+tdist[E]);
        }
    }
}

5-M

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int INF = 0x3f3f3f3f;
int p[102];
int n;
int value[102][102];
int w[102][102];

void show(int i, int j){
    if(j == i + 1){
        cout <<"(" << "A" << i << "A" << j << ")";
        return;
    }
    if(i == j){
        cout << "A" << i;
        return;
    }

    int k = w[i][j];
    if(i!=1||j!=n)
        cout << "(";
    show(i,k);
    show(k+1,j);
    if(i!=1||j!=n)
        cout << ")";
    return;
}

int main(){
    //freopen("input.txt","r",stdin);

    int t = 1;
    while(cin >> n){
        for(int i = 0;i<102;i++)
            for(int j = 0;j<102;j++)
                if(i == j)
                    value[i][j] = 0;
                else
                    value[i][j] = INF;

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

        for(int j = 2; j <= n; j++){
            for(int i = j - 1; i > 0; i--){
                for(int k = i; k < j; k++){
                    int temp = value[i][k] + value[k+1][j] + p[i-1]*p[k]*p[j];
                    if(value[i][j] > temp){
                        value[i][j] = temp;
                        w[i][j] = k;
                    }
                }
            }
        }
        cout << "Case " << t++ << endl;

        cout << value[1][n] << " ";
        if(n==2)
            cout << "A1A2";
        else
            show(1,n);
        cout << endl;
    }

    return 0;
}

cpp --- 1619 dijkstra

#include<iostream>
#include<math.h>
#include<vector>
#include<memory.h>
using namespace std;
#define inf 1e9+7
const int N = 55;
int G[N][N];
int dis[N];
bool book[N];
int main(){
    int n;
    int tcase=0;
    while(cin >> n){
        for(int i=0; i<N; i++){
            memset(G[i],0,sizeof(G[i]));
        }
        for(int i=0;i<n;i++){
            for(int j=0; j<n; j++){
                cin >> G[i][j];
                if(G[i][j] == -1){
                    G[i][j] = i==j?0:inf;
                }
            }
        }
        int s,t;
        cin >> s >> t;
        s--;t--;
        memset(dis,0,sizeof(dis));
        memset(book,0,sizeof(book));
        for(int i=0; i<n; i++){
            dis[i] = G[s][i];
        }
        book[s] = true;
        int u=0;
        for(int i=0; i<n; i++){
            //找到当前最短路
            int min = inf;
            for(int j=0; j<n; j++){
                if(!book[j] && dis[j]<min){
                    min = dis[j];
                    u = j;
                }
            }
            book[u] = true;
            //更新最短路
            for(int v=0; v<n; v++){
                if(G[u][v]<inf){
                    if(dis[u]+G[u][v] < dis[v]){
                        dis[v] = dis[u]+G[u][v];
                    }
                }
            }
        }
        cout << "Case " << ++tcase << endl;
        cout << dis[t] << endl;
    }
}

5-O

import java.math.*;
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while(in.hasNext()){
            int n = in.nextInt();
            if(n == 0){
                break;
            }
            System.out.println(n);
            System.out.println("Times:" + (int)Math.ceil(Math.log(n)*1.0/Math.log((3))));
        }
    }
}

1232

#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
    int a[1008],b[1008];
    int n;
    while(cin >> n){
        if(n==0) break;
        for(int i=0;i<n; i++)
            cin >> a[i];
        for(int i=0;i<n; i++)
            cin >> b[i];
        sort(a,a+n);
        sort(b,b+n);
        int i,j,c;
        i=j=c=0;
        while(i<n && j<n){
            if(a[i]>b[j]){
                c++;i++;j++;
            }
            else{
                i++;
            }
        }
        if(c>n/2)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

5-Q

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 110;
int p[maxn];
int h[maxn];
int dp[maxn];

int haha(){
    return 123;
}

int main(){
    int t;haha();
    cin>>t;haha();
    while(t--){
        int n;
        cin>>n;haha();
        memset(dp,INF,sizeof(dp));haha();
        /**记录节点从 1开始，思考更方便（统一dp和p，h的索引）*/
        for(int i = 1;i<=n;i++) cin>>p[i]>>h[i];
        /**初始化dp[0]是为dp[1]服务*/
        dp[0] = 0;haha();
        for(int i = 1;i<=n;i++){
            /*r和l的作用是不一样的，向左和向右的思路是不一样的。因为向右为正序，更新后的r
            为向右推倒的最大位置。向左为逆序，l表示当前要被推到的位置。所以在向右的时候else
            要break，因为再进行下去已经没有意义了。而向左则不一样，即使位置较大的p也可能推到当前的位置。
            这样就有一个弊端，dp[i]并不一定为推到i的最小次数（好像也没什么卵用）不用管**/
            int r = p[i]+h[i];haha();
        for(int j = i;j<=n;j++){
            if(p[j]<r){
                dp[j] = min(dp[j],dp[i-1]+1);
                r = max(p[j]+h[j],r);
            }
            else    break;
        }
        int l = p[i];haha();
        for(int j = i;j<=n;j++){
            if(p[j] - h[j] < l){
                dp[j] = min(dp[j],dp[i-1]+1);
                l = p[j];
            }

        }
        }
        cout<<dp[n]<<endl;haha();
    }
    return 0;
}

java---1539

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            long m = scanner.nextLong();
            long n = scanner.nextLong();
            long i=0;
            while(i<n){
                m++;
                if(m%7==0 || String.valueOf(m).contains("7")){
                    i++;
                }
            }
            System.out.println(m);
        }
    }
}

cpp --- 1572

dp问题

http://www.cnblogs.com/zhko11993/p/3806907.html

java---1679

特别鸣谢:xiaohuihui

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int mod = 1000007;
        long dp[][] = new long[405][405];
        dp[0][0] = dp[1][0] = dp[1][1] = 1;
        for(int i=2; i<401; i++){
            for(int j=0; j<=i; j++){
                if(j==0 || j==i)
                    dp[i][j] = 1;
                else
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%mod;
            }
        }


        int t = scanner.nextInt();
        while(t-- != 0){
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            if(k<2||k>m*n){
                System.out.println(0);
                continue;
            }
            long sum;
            sum = (dp[n*m][k] - 2*dp[(n-1)*m][k] - 2*dp[n*(m-1)][k]+mod)%mod;
            while(sum<0)sum+=mod;
            sum = (sum + dp[(n-2)*m][k] + dp[(m-2)*n][k] + 4 * dp[(n-1)*(m-1)][k])%mod;
            while(sum<0)sum+=mod;
            sum = (sum - 2*dp[(n-2)*(m-1)][k] - 2*dp[(m-2)*(n-1)][k]+mod)%mod;
            while(sum<0)sum+=mod;
            sum = (sum + dp[(n-2)*(m-2)][k])%mod;
            while(sum<0)sum+=mod;
            System.out.println(sum);
        }
    }
}

java---1074

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        BigInteger base = BigInteger.valueOf(17);
        while(scanner.hasNext()){
            BigInteger a = scanner.nextBigInteger();
            if(a.intValue()==0)break;
            if(a.mod(base).equals(BigInteger.ZERO))
                System.out.println("1");
            else
                System.out.println("0");
        }
    }
}

4-P

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX_N 555
#define MAX_M 555
int m,n;
int maps[MAX_M][MAX_N];
bool vis[MAX_M][MAX_N];

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

bool in(int x,int y)
{
    return x>=0&&y>=0&&x<m&&y<n;
}
int dfs(int r,int c)
{
    vis[r][c]=true;
    int res=0;
    for(int i=0;i<4;i++)
    {
        int x=r+dx[i];
        int y=c+dy[i];
        if(in(x,y)&&maps[x][y]==0&&!vis[x][y])
            res+=dfs(x,y);
    }
    return res+1;
}
void solvesss()
{
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
    {
        scanf("%d",&maps[i][j]);
        vis[i][j]=false;
    }
    int cnt=0;
    int ans=0;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
        {
            if(maps[i][j]==0&&!vis[i][j])
            {
                cnt++;
                ans=max(ans,dfs(i,j));
            }
        }
    printf("%d %d\n",cnt,ans);
}
int main()
{
   while(scanf("%d%d",&m,&n)==2)
   {
       solvesss();
   }
   return 0;
}

5-H

#include<iostream>
        #include<algorithm>
        #include<cstdio>
        #include<cstring>
        #define max(a,b) ((a)>(b)?(a):(b))
        using namespace std;

        int m[22][22][22];

        int dayangdfs(int a, int b, int c){
            if(a <= 0 || b <=0 || c <= 0)
                a = b = c = 0;
            if(a > 20 || b > 20 || c > 20)
                a = b = c = 20;
            if(m[a][b][c] != -1)
                return m[a][b][c];
            if(a <= 0 || b <= 0 || c <= 0)
                return (m[0][0][0] = 1);
            else if(a > 20 || b > 20 || c > 20)
                return (m[20][20][20] = dayangdfs(20,20,20));
            else if(a < b && b < c)
                return (m[a][b][c] = dayangdfs(a,b,c-1)+dayangdfs(a,b-1,c-1)-dayangdfs(a,b-1,c));
            else
                return (m[a][b][c] = dayangdfs(a-1,b,c)+dayangdfs(a-1,b-1,c)+dayangdfs(a-1,b,c-1)-dayangdfs(a-1,b-1,c-1));
        }

        int main(){
            //freopen("input.txt","r",stdin);

            int a,b,c;
            while(cin >> a >> b >> c){
                if(a == -1 && b == -1 && c == -1)
                    break;
                memset(m, -1, sizeof(m));

                cout << "w(" << a << ", " << b << ", " << c << ") = " << dayangdfs(a, b, c) << endl;

            }

            return 0;
        }

5-E

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

int main(){
    //freopen("input.txt", "r", stdin);

    int x[10000],y[10000];
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> x[i] >> y[i];
    sort(x, x + n);
    sort(y, y + n);

    int ans = 0;
    for(int i = 0, j = n - 1; i < j; i++, j--){
        ans+= x[j] - x[i] + y[j] - y[i];
    }

    cout << ans << endl;

    return 0;
}

5-F

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;

const int v = 2000 + 5;
const int MaxN = 100 + 5;
int N, sum, num[MaxN], dp[2][v];
int main() {
    int i, j, k;
    cin >> N;
    for(i = 0; i < N; ++i) {
        cin >> num[i];
        sum += num[i];
    }
    memset(dp, -1, sizeof(dp));
    dp[1][0] = 0;
    int a;
    for(i = 0; i < N; ++i) {
        a = i % 2;
        memset(dp[a], -1, sizeof(dp[a]));
        for(j = 0; j <= sum; ++j) {
            //1.不放第i块水晶;
            if(dp[a ^ 1][j] > -1)
                dp[a][j] = dp[a ^ 1][j];
            //2.放进去后，高塔变矮塔（第i块放在矮塔上了）;
            if(num[i] > j &&  dp[a ^ 1][num[i] - j] > -1)
                dp[a][j] = max(dp[a][j], dp[a ^ 1][num[i] - j] + j);
            //3.放进去后，高塔仍高（第i块放在矮塔上）;
            if(j + num[i] <= sum && dp[a ^ 1][j + num[i]] > -1)
                dp[a][j] = max(dp[a][j], dp[a ^ 1][j + num[i]]);
            //4.放进去后，高塔更高（第i块放在高塔上）.
            if(j >= num[i] && dp[a ^ 1][j - num[i]] > -1)
                dp[a][j] = max(dp[a][j], dp[a ^ 1][j - num[i]] + num[i]);
        }
    }
    if(dp[a][0] > 0)
        cout << dp[a][0] << endl;
    else
        cout << "Impossible" << endl;
}

5-G

import java.math.*;
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n,m;

        long a[] = new long[55];

        n = in.nextInt();
        m = in.nextInt();
        a[0] = 1;
        for(int i = 1; i <= n; i++){
            if(i < m) a[i] = 2*a[i-1];
            else if(i == m)
                a[i] = 2*a[i-1] - 1;
            else
                a[i] = 2 * a[i-1] - a[i - m -1];
        }
        System.out.println(a[n]);
    }
}

5-I

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

int vis[9][9];
int dir[4][2] = {{-1,2},{1,2},{-2,1},{2,1}};
int sx,sy;

struct Point
{
    int x,y;
    int step;
};

int in(int x, int y)
{
    return x>= 1&&x<=8&&y>=1&&y<=8;
}

int bfs()
{
    vis[sx][sy] = 1;
    queue<Point> q;
    Point start = {.x = sx, .y = sy, .step = 0};
    q.push(start);
    while(!q.empty())
    {
        Point p = q.front();
        q.pop();
        if(p.x == 8 && p.y == 8)
        {
            return p.step;
            break;
        }
        for(int i = 0; i < 4; i++)
        {
            int x = p.x + dir[i][0];
            int y = p.y + dir[i][1];
            if(in(x,y) && !vis[x][y])
            {
                Point t;
                t.x = x;
                t.y = y;
                t.step = p.step + 1;
                vis[x][y] = 1;
                q.push(t);
            }
        }
    }

    return -1;
}

int main()
{
    while(cin >> sx >> sy)
    {
        memset(vis, 0, sizeof(vis));
        int ans = bfs();
        if(ans >= 0)
        {
            cout << ans << endl;
        }else
        {
            cout << "Impossible" << endl;
        }
    }

    return 0;
}

4-O

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

int parent[33];


struct point{
    int x,y,z;
};

point points[33];

struct edge{
    int x,y;
    double len;
};

edge es[500];

bool cmp(edge a, edge b){
    return a.len < b.len;cout<<"";
}

double dist(point a, point b){
    return sqrt((a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y) +(a.z - b.z)*(a.z - b.z)+0.0);
}

int find(int i){
    return i == parent[i]? i : find(parent[i]);
}

int main(){
    //freopen("input.txt" , "r" , stdin);

    int T,n;
    cin >> T;
    edge t;
    while(T--){
        cin >> n;cout<<"";cout<<"";
        for(int i = 0; i < n; i++)
            parent[i] = i;
        for(int i = 0; i < n; i++){
            cin >> points[i].x >> points[i].y >> points[i].z;
        }
        int num = 0;cout<<"";
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                t.x = i;cout<<"";cout<<"";
                t.y = j;cout<<"";cout<<"";
                t.len = dist(points[i],points[j]);cout<<"";
                es[num++] = t;cout<<"";
            }
        }

        sort(es,es + num, cmp);
        double result = 0.0;
        for(int i = 0; i < num; i++){
            int p = find(es[i].x);cout<<"";
            int q = find(es[i].y);cout<<"";
            if(p != q){
                parent[p] = q;cout<<"";
                result += es[i].len;cout<<"";
            }
        }

        printf("%.2f\n",result);cout<<"";cout<<"";
    }

    return 0;
}

5-D

#include<stdio.h>
int p(int n);
int main()
{
    int n,m,i;

    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&m);
        printf("%d\n",computeStep(m));
    }

    return 0;

}
int computeStep(int n)
{
    int aaaa[50],i;

    aaaa[0]=aaaa[1]=1;
    for(i=2;i<n;i++)
        aaaa[i]=aaaa[i-1]+aaaa[i-2];
    return aaaa[n-1];
}

5-C

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 202;
int e_max[N][N];
int e[N];
int ans;

int main(){
    //freopen("input.txt", "r", stdin);

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> e[i];
        e[i+n] = e[i];
    }

    ans = 0;
    memset(e_max,0,sizeof(e_max));

     for (int i=2;i<n+n;i++) for (int j=i-1;j>=1 && i-j<n;j--) {
        for (int k=j;k<i;k++) {
            int tem=e_max[j][k]+e_max[k+1][i]+e[j]*e[k+1]*e[i+1];
            if (tem>e_max[j][i]) e_max[j][i]=tem;
        }
        if (e_max[j][i]>ans) ans=e_max[j][i];
    }

    cout << ans << endl;

    return 0;
}

5-B

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
bool ran(int x,int y)
{
     return x<y;
}
int main()
{
    //freopen("input.txt","r",stdin);
    int k,i,j;
    while(cin>>k)
    {
                 if(k==0) break;
                 int tj[1001],king[1001];
                 for(i=0;i<k;i++) cin>>tj[i];
                 for(i=0;i<k;i++) cin>>king[i];
                 sort(tj,tj+k,ran);
                 sort(king,king+k,ran);
                 long int count=0;
                 int tj_min=0,tj_max=k-1;
                 int king_min=0,king_max=k-1;
                 while(tj_min<=tj_max)
                 {
                                      if(tj[tj_max]>king[king_max])
                                      {
                                            count++;
                                            tj_max--;king_max--;
                                      }
                                      else if(tj[tj_min]>king[king_min])
                                      {
                                            count++;
                                            tj_min++;king_min++;
                                      }
                                      else
                                      {
                                            if(tj[tj_min]<king[king_max])
                                            count--;
                                            tj_min++;king_max--;
                                      }
                 }
                 if(count > k/2)
                    cout << "YES" << endl;
                 else
                    cout << "NO" << endl;
    }

    return 0;
}

cpp --- 1584

波利亚

快速幂

#include <bits/stdc++.h>

typedef long long LL;

int main() {
    //快速幂
    auto pm = [](int a, int x) {
        LL res = 1;
        LL t = a;
        while (x) {
            if (x & 1) res = res * t;
            t *= t;
            x >>= 1;
        }
        return res;
    };
    int n;
    while (std::cin >> n) {
        LL ans = 0;
        std::cout << (5 * pm(n, 6) + pm(n, 10) + 4 * pm(n, 2)) / 10 << std::endl;
    }
    return 0;
}

5-J

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int T,L,N;
int k[2005], f[2005];

int main()
{
    cin >> T;

    while(T--)
    {
        cin >> L >> N;
        for(int i = 0; i < N; i++)
            cin >> k[i];
        for(int i = 0; i < N; i++)
            cin >> f[i];

        int pos = 0;
        int s = 0x3f3f3f3f;
        for(int i = 0; i <= L; i++)
        {
            int sum = 0;
            for(int j = 0; j < N; j++)
            {
                int t = f[j] - abs(k[j] - i);
                sum += (t < 0 ? 0 : t);
            }
            if(sum < s)
            {
                s = sum;
                pos = i;
            }
        }
        cout << pos << " " << s << endl;
    }

    return 0;
}

cpp --- 1521

总的三角形数量减去非单色三角形数量

#include <bits/stdc++.h>

typedef long long LL;
int a[1005];
int main() {
    int t;
    std::cin >> t;
    while(t--){
        memset(a,0,sizeof(a));
        int m,n,x,y;
        std::cin >> n >> m;
        while(m--){
            std::cin >> x >> y;
            a[x-1]++;
            a[y-1]++;
        }
        LL sum=n*(n-1)*(n-2)/6;
        LL fail = 0;
        for(int i=0; i<n; i++){
            fail += (n-1-a[i])*a[i];
        }
        sum -= fail/2;
        std::cout << sum << std::endl;
    }
    return 0;
}

5-A

import java.util.*;
public class Main{

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        double a;
        while(in.hasNext()){
            a = in.nextDouble();
            System.out.printf("%.3f\n",4*Math.PI*Math.pow(a,3)/3);
        }
    }
}

4-D

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
#include <vector>
using namespace std;

const int INF = 99999999;
const int N = 1005;

vector<int> road[N];    //定义一个向量（第一次用-O(∩_∩)O-）
int map[N][N], dist[N], s[N];
bool visit[N];
int n, t, sum;

void init()
{
    int i, j;cout<<"";
    sum = 0;cout<<"";
    memset(s, 0, sizeof(s));cout<<"";
    for(i = 0; i <= n; i++) road[i].clear();cout<<"";
    for(i = 0; i <= n; i++)
        for(j = 0; j <= n; j++)
            if(i == j) map[i][j] = 0;
            else map[i][j] = INF;
}

void input()
{
    int a, b, d;
    while(t--)
    {cout<<"";
        scanf("%d %d %d", &a, &b, &d);
        if(d < map[a][b])
        {cout<<"";
            map[a][b] = map[b][a] = d;  //双向的cout<<"";
            road[a].push_back(b);cout<<"";
            road[b].push_back(a);cout<<"";
        }cout<<"";
    }
}

void spfa()     //比较喜欢用spfa
{
    int i, now;cout<<"";
    memset(visit, false, sizeof(visit));cout<<"";
    for(i = 1; i <= n; i++) dist[i] = INF;
    dist[2] = 0;
    queue<int> Q;cout<<"";
    Q.push(2);
    visit[2] = true;cout<<"";
    while(!Q.empty())
    {
        now = Q.front();
        Q.pop();
        visit[now] = false;cout<<"";
        for(i = 1; i <= n; i++)
        {cout<<"";
            if(dist[i] > dist[now] + map[now][i])
            {cout<<"";
                dist[i] = dist[now] + map[now][i];
                if(visit[i] == false)
                {
                    Q.push(i);
                    visit[i] = true;
                }cout<<"";
            }
        }
    }
}

int dfs(int now)    //记忆化搜索
{
    int i;cout<<"";
    if(now == 2) return 1;  //找到终点，返回1（1条路）
    if(s[now]) return s[now];   //该点已经走过，返回：过该点有多少条路
    for(i = 0; i < road[now].size(); i++)
    {
        if(dist[now] > dist[ road[now][i] ])
        {
            s[now] += dfs(road[now][i]);cout<<"";
        }
    }
    return s[now];  //返回：该点一共可以有多少条路
}

int main()
{
    while(scanf("%d", &n), n)
    {
        scanf("%d", &t);
        init();cout<<"";
        input();cout<<"";
        spfa();cout<<"";
        sum = dfs(1);   //sum一共多少条路，sum = s[1] 也行
        printf("%d\n", sum);
    }

    return 0;
}

cpp --- 1998 哦我的天

#include <bits/stdc++.h>

int main() {
    int T;
    std::cin >> T;
    while (T --) {
        int n;
        std::cin >> n;
        std::cout << (1 << __builtin_popcount(n)) << std::endl;
    }
    return 0;
}

java---1532

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            BigInteger a = scanner.nextBigInteger();
            BigInteger b = scanner.nextBigInteger();
            System.out.println(a.gcd(b.pow(b.intValue())));
        }
    }
}

5-N

import java.math.*;
import java.util.*;
public class Main{

    public static int m;
    public static int n;
    public static int[][] a;

    public static int getCommonLength(char[] s1, char[] s2){

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s1[i-1] == s2[j-1]){
                    a[i][j] = a[i-1][j-1] + 1;
                }else{
                    a[i][j] = Math.max(a[i-1][j],a[i][j-1]);
                }
            }
        }
        return a[m][n];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int T = Integer.parseInt(in.nextLine());
        int k = 1;
        while(T-- > 0){
            String[] s = in.nextLine().split(" ");
            m = Integer.parseInt(s[0]);
            n = Integer.parseInt(s[1]);
            a = new int[m+1][n+1];

            for(int i = 0; i <= m; i++){
                a[i][0] = 0;
            }

            for(int j = 0; j <= n; j++){
                a[0][j] = 0;
            }

            char[] s1 = in.nextLine().replaceAll(" ","").toCharArray();
            char[] s2 = in.nextLine().replaceAll(" ","").toCharArray();

            System.out.println("Case " + (k++));
            System.out.println(getCommonLength(s1,s2));
        }
    }
}

5-R

#include<iostream>  
#include<algorithm>  
using namespace std;  
struct Apple  
{  
    int d,num;  
};  
bool cmp(Apple a,Apple b)  
{  
    return a.d<b.d;  
}  
int haha(){
    return 123;
}
int main(void)  
{  
    int b,l,t,i,n,k,far;  
    Apple apple[1005];  
    cin>>t;  haha();
    while(t--)  
    {  
        cin>>n>>k;  
        b=0;  haha();
        l=0;  haha();
        for(i=1;i<=n;i++)  
            cin>>apple[i].d>>apple[i].num;  
        i=n;  
        far=n;  haha();
        sort(apple+1,apple+n+1,cmp);  haha();
        while(apple[1].num!=0)  
        {  
            if(apple[i].num>k-b)  
            {  
                apple[i].num-=k-b;  haha();
                b=0;  haha();
                l+=apple[far].d*2;  haha();
                far=i;  haha();
            }  
            else if(apple[i].num==k-b)  
            {  
                l+=apple[far].d*2;  
                b=0;  
                apple[i].num=0;  
                i--;  haha();
                far=i;  haha();
            }  
            else 
            {  
                b+=apple[i].num;  haha();
                apple[i].num=0;  haha();
                if(i==1)  
                    l+=apple[far].d*2;  
                i--;  
            }  
        }  
        cout<<l<<endl;  
    }  
    return 0;  
}

zhaokuohaha / 2016summerprogramdesign Goto Github PK

2016summerprogramdesign's Introduction

2016SummerProgramDesign

代码直接贴在issues里面

2016summerprogramdesign's People

Contributors

Watchers

2016summerprogramdesign's Issues

Recommend Projects

Recommend Topics

Recommend Org