【2012长春区域赛】部分题解 hdu4420—4430

这场比赛特点在于两个简单题太坑，严重影响了心情。。导致最后只做出两题....当然也反映出心理素质的重要性

1002：

题意：一个矩阵b[n][n]通过数组 a[n]由以下规则构成，现在已知b[n][n]问是否有对应的数组a[n]

解法：

首先都是位运算所以不同位是不会互相影响的，即可按位考虑。

又发现，只要知道a[0]就可以算出通过b[0][]算出所有的a[]，这样可以假设a[0]为0或1，由b[0][]得到一个完整的数组a[]，再check这个数组a是否能正确的得到其他的b[][]即可

时间复杂度约为32*2*n^2 对于n=1000是可以接受的

当然队友是用2-SAT做的 吊吊吊吊吊orz 我就没写了，这里贴上队友的代码

代码：

#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include <stdio.h>
using namespace std;

const int maxn = ;

struct TwoSAT
{
    int n;
    vector<int> G[maxn * ];
    bool mark[maxn * ];
    int S[maxn * ], c;

    bool dfs(int x)
    {
        if(mark[x ^ ]) return false;
        if(mark[x]) return true;
        mark[x] = true;
        S[c++] = x;
        for(int i = ; i < G[x].size(); i++)
            if(!dfs(G[x][i])) return false;
        return true;
    }

    void init(int n) // 一定要注意初始化的点数，别弄错
    {
        this->n = n;
        for(int i = ; i < n * ; i++) G[i].clear();
        memset(mark, , sizeof(mark));
    }

    // x = xval or y = yval
    void add_clause(int x, int xval, int y, int yval) // 编号从0~n-1
    {
        x = x *  + xval;
        y = y *  + yval;
        G[x ^ ].push_back(y);
        G[y ^ ].push_back(x);
    }

    // 当x==xval 时可推导出 y==yval
    void add_edge(int x, int xval, int y, int yval)
    {
        x = x *  + xval;
        y = y *  + yval;
        G[x].push_back(y);
    }

    bool solve()
    {
        for(int i = ; i < n * ; i += )
            if(!mark[i] && !mark[i + ])
            {
                c = ;
                if(!dfs(i))
                {
                    while(c > ) mark[S[--c]] = false;
                    if(!dfs(i + )) return false;
                }
            }
        return true;
    }
};

TwoSAT solver;
int n;
int a[maxn][maxn];

bool check(int l)
{
    solver.init(n);
    for(int i = ; i < n; i++)
        for(int j = ; j < n; j++)
        {
            int bit = (a[i][j] & ( << l))>>l;

            if(i == j)
            {
                if(a[i][j] != )
                {
                    return false;
                }
            }
            else if(a[i][j] != a[j][i])
            {
                return false;
            }
            else if(i %  ==  && j %  == ) // &
            {
                solver.add_edge(i, , j, bit);
                solver.add_edge(j, , i, bit);
                if(bit)
                {
                    solver.add_edge(i, , i, );
                    solver.add_edge(j, , j, );
                }
            }
            else if(i %  ==  && j %  == ) // |
            {
                solver.add_edge(i, , j, bit);
                solver.add_edge(j, , i, bit);
                if(!bit)
                {
                    solver.add_edge(i, , i, );
                    solver.add_edge(j, , j, );
                }
            }
            else // ^
            {
                solver.add_edge(i, , j, bit ^ );
                solver.add_edge(j, , i, bit ^ );
                solver.add_edge(i, , j, bit);
                solver.add_edge(j, , i, bit);
            }
        }
    return solver.solve();
}

int main()
{

    while(~scanf("%d", &n))
    {
        for(int i = ; i < n; i++)
            for(int j = ; j < n; j++)
            {
                scanf("%d", &a[i][j]);
            }
        bool flag = true;
        // 枚举每一位,l为座椅的 位数
        for(int l = ; l <= ; l++)
        {
            if(!check(l))
            {
                flag = false;
                break;
            }
        }
        puts(flag?"YES":"NO");
    }

    return ;
}

1003：

题意：

这个简单题题意挺恶心的。。先开始一直没读懂。。

小明要在五座山上采五堆蘑菇，每堆的个数是0~2012，采完后必须送出三堆和为1024倍数的蘑菇（否则全送出），回家之前如果总数大于1024还要一直被抢1024。

现在已经采了n堆（n<=5），剩下的可以任意采（0~2012）问最终最多能拿回家多少蘑菇.

解法：

分情况特判.....以下省略好多字

代码：

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
int a[];
const int mod = ;
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    int n;
    while (~scanf ("%d", &n))
    {
        memset(a, , sizeof(a));
        int sum = ;
        for (int i = ; i < n; i++)
        {
            scanf ("%d", a+i);
            sum += a[i];
        }
        int ans = , res = ;
        if (n<=)
        {
            printf("%d\n", );
            continue;
        }
        if (n == )
        {
            int ans = ;
            bool flag = ;
            for (int i = ; i < ; i++)
            {
                for (int j = i+; j < ; j++)
                {
                    int tmp = a[i]+a[j];
                    if (tmp)
                    ans = max(ans, (tmp%) ? (tmp%) : );
                    for (int k = j +; k < ; k++)
                    {
                        if ((a[i] + a[j] + a[k]) %  == )
                            flag = ;
                    }
                }
            }
            if (flag)
                printf("%d\n" , );
            else
                printf("%d\n" ,ans);
            continue;
        }
        if (n == )
        {
            bool f = ;
            int  ans = ;
            for (int i = ; i < ; i++)
            {
                for (int j = i+; j < ; j++)
                {
                    for (int k = j+; k < ; k++)
                    {
                        int tmp = a[i] +a[j] +a[k];
                        if (tmp %  == )
                        {
                            if (sum-tmp)
                            ans = max(ans, ((sum-tmp)%) ? (sum-tmp)% : );
                        }
                    }
                }
            }
            printf("%d\n",(ans > ) ? (ans %) : ans);
        }
    }
    return ;
}

1004：

题意：

 求y的取值范围

思路：

高中数学题，移项得到一个二次函数，然后各种分类讨论，太麻烦了没敢写。。。

1005：

题意：

一颗给定的无根树里面有边权，要求选定一个根使得此根到所有节点的代价最大，代价定义为路径上边权的最小值

解法：

奇怪的贪心，先按边权大到小排序，然后加边，并查集维护，每次合并的时候贪心的取代价最小（还是不知道为什么是对的）

代码：

 #include <set>
 #include <map>
 #include <cmath>
 #include <ctime>
 #include <queue>
 #include <stack>
 #include <cstdio>
 #include <string>
 #include <vector>
 #include <cstdlib>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;
 typedef unsigned long long ull;
 typedef long long ll;
 const int inf = 0x3f3f3f3f;
 const double eps = 1e-;
 const int maxn = 2e5+;
 int pa[maxn],rnk[maxn];
 struct Edge
 {
     int frm, to, cst;
     bool operator < (const Edge &rhs)const
     {
         return cst > rhs.cst;
     }
 }e[maxn];
 int find (int x)
 {
     return pa[x] = (pa[x] == x ? x : find(pa[x]));
 }
 ll ans[maxn];
 void Merge(int x, int y, int cost)
 {
     int fx = find(x);
     int fy = find(y);
     if (rnk[fx] < rnk[fy])
         swap(fx, fy);
     ans[fx] = max(ans[fy]+(ll)rnk[fx]*cost, ans[fx]+(ll)rnk[fy]*cost);
     pa[fy] = fx;
     rnk[fx] += rnk[fy];
 }
 void init ()
 {
     memset(ans, , sizeof(ans));
     for (int i = ; i < maxn; i++)
     {
         pa[i] = i;
         rnk[i] = ;
     }
 }
 int main()
 {
     #ifndef ONLINE_JUDGE
         freopen("in.txt","r",stdin);
     #endif
     int n;
     while (~scanf ("%d", &n))
     {
         int u, v, c;
         init();
         for (int i = ; i < n-; i++)
         {
             scanf ("%d%d%d", &u, &v, &c);
             e[i].frm = u, e[i].to = v, e[i].cst = c;
         }
         sort (e,e+n-);
         for (int i = ; i < n-; i++)
         {
             Merge(e[i].frm, e[i].to, e[i].cst);
         }
         printf("%I64d\n", ans[find()]);
     }
     return ;
 }

1008：

题意：

知道n个数的和sum，以及n个数的LCM，求合法的组成方案（排列）

解法：
发现lcm的转移只可能通过lcm的约数，（一开始和分解质因数搞呢，后来经过学长提醒发现直接找出约数即可 orz），约数数量不是很多。。这样就可以dp了

把约数哈希一下 dp[i][j][k]代表考虑到第i个数，当前lcm为总LCM的第j个约数，当前sum为k的方案数，转移很容易

代码：

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
const int mod=1e9+;
bool is(int p)
{
    for(int i=; i*i<=p; i++)
    {
        if(p%i==)
            return ;
    }
    return ;
}
int gcd(int a,int b)
{
    return b==?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
int prime[];
int s[];
int dp[][][];
int a[];
int ha[];
int l[][];
int sum,L,n,m;
int main()
{
   // freopen("in.txt","r",stdin);
    m=;
    for(int i=; i<=; i++)
    {
        if(is(i))
        {
            prime[m++]=i;
        }
    }
    while(scanf("%d%d%d",&sum,&L,&n)!=EOF)
    {
        memset(ha,-,sizeof(ha));
        int lim=;
        for(int i=;i<=L;i++)
        {
            if(L%i==)
            {
                ha[L/i]=lim;
                s[lim++]=L/i;
            }
        }
        for(int i=;i<lim;i++)
        {
            for(int j=;j<lim;j++)
            {
                l[i][j]=lcm(s[i],s[j]);
            }
        }
        memset(dp,,sizeof(dp));
        dp[][][lim-]=;
        for(int i=;i<=n;i++)
        {
            for(int j=;j<=sum;j++)
            {
                for(int k=;k<lim;k++)
                {
                    if(!dp[i-][j][k])
                        continue;
                    for(int t=;t<lim;t++)
                    {
                        if(j+s[t]<=sum)
                        {
                            if(ha[l[k][t]]==-)
                                continue;
                            dp[i][j+s[t]][ha[l[k][t]]]+=dp[i-][j][k];
                            dp[i][j+s[t]][ha[l[k][t]]]%=mod;
                        }
                    }
                }
            }
        }
        cout<<dp[n][sum][]<<endl;
    }
    return ;
}

1010：

题意：
一个大矩形被一些线段分成了小矩形，现在给定两个点的坐标，求出删除一些线段使这两点在同一矩形后剩余矩形数量的最大值。

思路：

其实就是要找所求两点共同所在的最小的矩形（除此之外的线段都不删除，得到的剩余矩形数肯定最多）。

而按照题意的分割矩形法其实就是形成了一颗树，这样就发现两个点所在的最小矩形其实是这两个点当前所在矩形的lca

理论ac了。。代码还没写

1011:

题意：

给定一个等比数列 1(或者0)+k+k^2+....k^r的和 S，要求求出r 和k，多解首先满足r*k最小，然后满足 r最小

解法：

由于k>=2所以可以计算发现r最大为40，则可以枚举r，二分求得k ，如果r和二分出的k刚好等于 k或者k-1 则符合题意，可以统计答案

坑点是二分过程中容易溢出

代码：

#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;

ll n;

ll equ(ll ak , int r)
{
    ll ans = ;
    ll k = ak;
    for(int i = ; i <= r; i++)
    {
        ans += k;
        if(ans > n + )
            break;
        if(ans<=)
            return 10000000000000LL;
        k *= ak;
    }
    return ans;
}

int main()
{

    while(~scanf("%I64d", &n))
    {
        ll ansk = 10000000000000LL;
        int ansr = ;

        // 枚举r
        for(int r = ; r <= ; r++)
        {
            // 二分k
            ll l = , R = 1000000000001LL;
            while(l < R)
            {
                ll m = (l + R + ) / ;
                if(equ(m, r) <= n)
                {
                    l = m;
                }
                else
                {
                    R = m - ;
                }
            }

            ll k = l;
            if(equ(k, r) == n)
            {
                // 保存答案
                if((ansk * ansr > k * r) || ((ansk * ansr == k * r) && ansr > r))
                {
                    ansk = k;
                    ansr = r;
                }
            }

            // 二分k
            l = , R = 1000000000001LL;
            while(l < R)
            {
                ll m = (l + R + ) / ;
                if(equ(m, r) <= n + )
                {
                    l = m;
                }
                else
                {
                    R = m - ;
                }
            }

            k = l;
            if(equ(l, r) == n + )
            {
                // 保存答案
                if((ansk * ansr > k * r) || ((ansk * ansr == k * r) && ansr > r))
                {
                    ansk = k;
                    ansr = r;
                }
            }
        }
        printf("%d %I64d\n", ansr, ansk);
    }

    return ;
}