test20190811 Solution

T1 WA水井

算法1:

显然是一棵最小生成树,考虑每一块稻田都需引入水,总共有n块田,因此总共需要安装n个东西,这个东西可以是水管也可以是井。

那么我们就将每一口井和每一条水管变成一条边,

  • 如果在稻田$i$挖一口井,则将这条边起点设为$i$,终点设为0,权值即为$w[i]$;
  • 如果修建一条水管连接$i$和$j$,则将这条边起点设为$i$,终点设为$j$,权值即为$p[i][j]$.

建完图跑一遍kruskal就可以了,注意重边只加一次

代码:(致命压行,不喜亲喷)

#include <bits/stdc++.h>
#define FOR(ij, l, n) for (ij = l; ij <= n; ++ij)
using namespace std;
struct Dot {
    int from, to, w;
    bool operator < (const Dot & rhs) const {return w > rhs.w;}
}t;const int N = 300;
int n, i, j, x, y, ans, fa[N + 30], len;
int get(int d);
priority_queue < Dot > Q;
int main() {
      freopen("water.in", "r", stdin);
      freopen("water.out", "w", stdout);
    scanf ("%d", &n); len = n;
    FOR(i, 1, n) fa[i] = i;
    FOR(i, 1, n) {scanf ("%d", &x); Q.push((Dot){i, 0, x});}
    FOR(i, 1, n) FOR(j, 1, n) {
        scanf ("%d", &x);
        if (i < j) Q.push((Dot){i, j, x});
    }while (!Q.empty() && len) {
        t = Q.top(); Q.pop();
        if (get(t.from) == get(t.to)) continue;
        fa[get(t.from)] = get(t.to);
        ans += t.w; --len;
    }printf ("%d\n", ans);
    return 0;
}int get(int d) {
    if (fa[d] == d) return d;
    else return fa[d] = get(fa[d]);
}

T2

一棵二叉搜索树。

保存两个祖先值,大于当前树上某结点树就向右,不然就向左,更新祖先值即可。本次最水。

#include <bits/stdc++.h>
using namespace std;
double n,m;
int flag=0;
void dfs(double now1,double now2,double last1,double last2){
    int x1,x2;
    x1=now1;
    x2=now2;
    now1+=last1;
    now2+=last2;
    if (n==now1 && m==now2) return;
    if (n/m<now1/now2){
        cout<<'L';
        if (flag==1){
            flag=1;
            dfs(now1,now2,last1,last2);
        }
        else {flag=1;dfs(now1,now2,x1,x2);}
    }
    else {
        cout<<'R';
        if (flag==1){
            flag=0;
            dfs(now1,now2,x1,x2);
        }
        else {
            flag=0;
            dfs(now1,now2,last1,last2);
        }
    }
}
int main(){
    freopen("fraction.in","r",stdin);
    freopen("fraction.out","w",stdout);
    cin>>n>>m;
    if (n/m<1) {flag=1;cout<<'L';dfs(1,1,0,1);}
    else {flag=0;cout<<'R';dfs(1,1,1,0);}
    cout<<endl;
    return 0;
}

T3兔八哥与猎人

(by czy)

  • 如果两点的横坐标差打绝对值和纵坐标差打绝对值的最大公因数是1,代表两点之间没有其他树(斜率),输出no
  • 否则输出yes注意特判gcd的两个数不能为0
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long x,long long y){
    if(x % y == 0)return y;
    return gcd(y,x % y);
}
int main(){
    freopen("rabbit.in","r",stdin);
    freopen("rabbit.out","w",stdout);
    long long n;
    cin>>n;
    for(long long i = 1;i <= n;i++){
        long long a,b,x,y;
        cin>>a>>b>>x>>y;
        if(a == x && abs(b - y) <= 1){
            cout<<"no"<<endl;
            continue;
        }
        if(b == y && abs(a - x) <= 1){
            cout<<"no"<<endl;
            continue;
        }
        if(b != y && a != x && gcd(abs(a - x),abs(b - y)) == 1)cout<<"no"<<endl;
        else cout<<"yes"<<endl;
    }
    return 0;
}

T4 运动会

(by fpjo)

  • 题目大意:求n个人,每组人不少于k个,共有多少种方案。
  • 思路1:可以枚举……就是爆搜(然后60')
    但是记忆化搜索可以啊!!!记录当人数为sum,不少于k时的情况,搜索即可
#include<bits/stdc++.h>
using namespace std;
int const mod=10000007;
int n,K,tar,ans;
int an[500][500];
int dfs(int sum,int k){
    if(an[sum][k])return an[sum][k];
    int ans=1;
    for(int i=k;i<=n;i++){
        if(sum>=2*i){
            ans+=dfs(sum-i,i);
            ans%=mod;
        }
    }
    return an[sum][k]=ans;
}
int main(){
    freopen("group.in","r",stdin);
    freopen("group.out","w",stdout);
    scanf("%d%d",&n,&K);
    printf("%d\n",dfs(n,K));
    return 0;
}
  • 思路2:dp。一般来说,有记忆化搜索的解法,也会有dp的解法(似乎有人说过)可我dp弱爆了
    只好贴lyh大佬的题解了

dp题解.png

T5

Last modification:August 12th, 2019 at 10:04 pm

Leave a Comment