ural 1091. Tmutarakan Exams 和 codeforces 295 B. Greg and Graph

时间：2021-01-12 21:10:21

ural 1091 题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1091

题意是从1到n的集合里选出k个数，使得这些数满足gcd大于1

解法：

因子有2的数： 2，4，6，8，10，12，14.。。

因子有3的数：3，6，9，12，15，18，21.。。

因子有5的数：5，10，15，18，21，24.。。

可以看出这里求出的集合时会有重复的，得去从。可惜没有学过容斥原理。不过解决这题还是没问题的。

50以内的素因子有：2， 3， 5， 7， 11， 13， 17， 19， 23只有这些素因子才可能产生集合元素大于2的集合

排除重复度为2的集合： 6{2，3(因子2和因子3造成集合重复)}， 10{2，5}，14{2，7}， 22{2， 11}， 15{3，5}，21{3，7}

代码为：

IN = lambda : map(int, raw_input().split() )

prime = [2, 3, 5, 7, 11, 13, 17, 19, 23]

x = [6, 10, 14, 22, 15, 21]

k, s = IN()

c =[ [0]*(s+1) for i in xrange(s+1) ]

for i in xrange(s+1):

    c[i][1] = i; c[i][0] = 1; c[i][i]=1

for i in xrange(1,s+1):

    for j in xrange(1, i):

        c[i][j] = c[i-1][j]+c[i-1][j-1]

sum = 0

for v in prime:

    if s/v<k: break

    sum += c[s/v][k]

for v in x:

    if s/v<k: break

    sum -= c[s/v][k]

print sum if sum<10000 else 10000

cf 295B http://codeforces.com/problemset/problem/295/B

题意是：按照一定顺序删除点并删除与点相连的线，求删除该点前的点集合里两两点的最短距离。

这题我以前看到过类似的，很自然就想到了从后往前处理，每次把这个点加进去循环更新距离，这个类似floyed

python代码：肯能是python效率问题吧，这个代码过不了。TLE，但是换成c++就过了

from sys import stdin,stdout

IN = lambda: [ int(x) for x in stdin.readline().split()  ]

n = int( stdin.readline().strip() )

edge = []

for i in xrange(n):

        edge.append( IN() )

x = IN()

ans = [0]*n

for k in xrange(n-1, -1, -1):

        for i in xrange(n):

                for j in xrange(n):

                        edge[i][j] = min( edge[i][j], edge[i][x[k] -1] + edge[x[k]-1 ][j] )

        for i in xrange(k, n):

                for j in xrange(k, n):

                        ans[k] += edge[x[i]-1 ][x[j]-1 ]

print ' '.join( map(str,ans ) )

c++ code：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define maxn 505

int n, edge[maxn][maxn];

int x[maxn];

long long ans[maxn];

int main(int argc, char**argv){

    cin >> n;

    for ( int i=; i<n; ++i )

            for ( int j=; j<n; ++j )

            cin >> edge[i][j];

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

    for ( int k=n-; k>=; --k ){

        for ( int i=; i<n; ++i )

            for ( int j=; j<n; ++j )

            edge[i][j] = min( edge[i][j], edge[i][x[k]- ]+ edge[x[k]-][j] );

        ans[k] = ;

        for ( int i=k; i<n; ++i )

            for ( int j=i+; j<n; ++j )

            ans[k] += edge[x[i]- ][x[j]- ]+edge[x[j]- ][x[i]- ];

    }

    for ( int i=; i<n; ++i )

         printf("%I64d ", ans[i]);

}

相关文章