福州大学第十一届程序设计竞赛部分题目题解

超、凢脫俗 2022-08-27 01:28 221阅读 0赞

比赛链接：http://acm.fzu.edu.cn/contest/index.php?cid=139

当今天下午我知道有这个比赛的时候，比赛已经开始20分钟了。。。。

中午早睡早起本来是准备复习考试的，结果比赛以及赛后补题消耗了大量时间，搞得我现在有一种要挂科的预感。。。。

<table> 
 <tbody> 
  <tr> 
   <td><img src="http://acm.fzu.edu.cn/image/ac.gif" alt=""></td> 
   <td>1</td> 
   <td><a href="http://acm.fzu.edu.cn/contest/problem.php?cid=139&amp;sortid=1" rel="nofollow">大王叫我来巡山呐</a></td> 
   <td>80.31%(261/325)</td> 
  </tr> 
  <tr> 
   <td><img src="http://acm.fzu.edu.cn/image/ac.gif" alt=""></td> 
   <td>2</td> 
   <td><a href="http://acm.fzu.edu.cn/contest/problem.php?cid=139&amp;sortid=2" rel="nofollow">防守阵地 I</a></td> 
   <td>23.48%(193/822)</td> 
  </tr> 
  <tr> 
   <td><img src="http://acm.fzu.edu.cn/image/ac.gif" alt=""></td> 
   <td>3</td> 
   <td><a href="http://acm.fzu.edu.cn/contest/problem.php?cid=139&amp;sortid=3" rel="nofollow">shadow</a></td> 
   <td>13.23%(97/733)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>4</td> 
   <td><a href="http://acm.fzu.edu.cn/contest/problem.php?cid=139&amp;sortid=4" rel="nofollow">花生的序列</a></td> 
   <td>12.07%(21/174)</td> 
  </tr> 
  <tr> 
   <td><img src="http://acm.fzu.edu.cn/image/ac.gif" alt=""></td> 
   <td>5</td> 
   <td><a href="http://acm.fzu.edu.cn/contest/problem.php?cid=139&amp;sortid=5" rel="nofollow">防守阵地 II</a></td> 
   <td>14.98%(68/454)</td> 
  </tr> 
  <tr style="background-color:#d7d7ff"> 
   <td>&nbsp;</td> 
   <td>6</td> 
   <td><a href="http://acm.fzu.edu.cn/contest/problem.php?cid=139&amp;sortid=6" rel="nofollow">巡了南山我巡北山</a></td> 
   <td>0.00%(0/45)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>7</td> 
   <td><a href="http://acm.fzu.edu.cn/contest/problem.php?cid=139&amp;sortid=7" rel="nofollow">Nostop</a></td> 
   <td>20.79%(21/101)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>8</td> 
   <td><a href="http://acm.fzu.edu.cn/contest/problem.php?cid=139&amp;sortid=8" rel="nofollow">卷福的难题</a></td> 
   <td>10.00%(1/10)</td> 
  </tr> 
 </tbody> 
</table>

这里还有一份题解：http://blog.csdn.net/ok\_again/article/details/24595453

我后面的D题的代码就是参考它的。

第七题后来也过了，比赛时已经基本想出来了，但不知道为什么就是过不了，赛后学长讲给我思路发现出入不大。学长用了n次 Ctrl+Z 之后终于是找到了它的代码，对拍，发现自己写矩阵时有一个细节以前没注意到：

当进行快速幂的时候应该将新矩阵对角线初始化为1，这样矩阵相乘时才能保持不变（这句是写给自己看的，大家写法不同不必深究）。

当矩阵相乘的时候应该将对角线初始化为0，因为需要一个全新的矩阵来存储数据！

**FZU 2167 大王叫我来巡山呐**

#include <cstdio>
    
    int main ()
    {
        int n;
        while (~scanf("%d",&n))
        {
            int sum=n/7*2;
            int last=n%7;
            if (last==6)
                sum++;
            printf("%d\n",sum);
        }
        return 0;
    }

**FZU 2168 防守阵地 I**

这个题需要推导一下递推关系，推出来直接实现就好了，没什么陷阱

#include <cstdio>
    #include <cstring>
    
    #define upmax(a,b) ((a)=(a)>(b)?(a):(b))
    
    const int N=1000005;
    
    long long data[N];
    long long sum[N];
    
    int main ()
    {
        int n,m;
        while (~scanf("%d%d",&n,&m))
        {
            memset(data,0,sizeof(data));
            memset(sum,0,sizeof(sum));
            long long i,tmp,ji=0;
            for (i=0;i<n;i++)
            {
                scanf("%lld",&data[i]);
                if (i==0) sum[i]=data[i];
                else sum[i]=sum[i-1]+data[i];
    
                if (i<m) ji+=data[i]*(i+1); //值
            }
            long long tot=ji;
            for (i=m;i<n;i++)
            {
                tmp=sum[i-1]-sum[i-1-m];
                ji=ji-tmp+data[i]*m;
                if (tot<ji) upmax(tot,ji);
            }
            printf("%lld\n",tot);
        }
        return 0;
    }

**FZU 2169 shadow**

DFS即可解决，回溯的时候将多加的部分减掉。

记得需要双向加边，所以边数组需要2倍大小。DFS时传递父节点避免搜回去。

#include <cstdio>
    #include <cstring>
    #define min(x,y) ((x)<(y)?(x):(y))
    #define max(x,y) ((x)>(y)?(x):(y))
    using namespace std;
    
    const int N=100005;
    
    bool good[N]; //有军队
    int bad[N];  //敌军数量
    long long sum=0;
    int head[N],e;
    
    struct Edge
    {
    	int v,next;
    }edges[2*N];
    
    int DFS (int u,int val,int father)
    {//当前点，当前累计价值，父节点
        if (good[u])
        {
            sum+=val;
        }
        int son=0;
        if (good[u]) son++;
        for (int i=head[u];i != -1; i=edges[i].next)
            if (edges[i].v!=father)
                son+=DFS(edges[i].v,val+bad[u],u);
        if (son>1)
            sum-=(son-1)*bad[u];
        return son;
    }
    
    void Add (int u,int v)
    {
        edges[e].v=v;
        edges[e].next=head[u];
        head[u]=e++;
    }
    
    int main ()
    {
        int n,k;
        while (~scanf("%d%d",&n,&k))
        {
            memset(good,false,sizeof(good));
            memset(bad,0,sizeof(bad));
            memset(head,-1,sizeof(head));
            int i,a;
            for (i=1;i<=n;i++)
                scanf("%d",&bad[i]);
            for (i=0;i<k;i++)
            {
                scanf("%d",&a);
                good[a]=true;
            }
            sum=0;
            for (i=0;i<n-1;i++)
            {
                int u,v;
                scanf("%d%d",&u,&v);
                Add(u,v);
                Add(v,u);
            }
            int son=0;
            DFS(1,0,-1);
            printf("%lld\n",sum);
        }
        return 0;
    }

**FZU 2170 花生的序列**

这个题当时没有做出来。

dp\[i\]\[j\]，表示到第i为为止，有j个属于第一个串，因为串的特殊性（WBWBWB），所以很容易判断当前位置的字母满足的情况。比如当前j为奇数，那么j后面肯定只能接B。

使用滚动数组节省内存。

#include <cstdio>
    #include <cstring>
    
    const int N = 10005;
    const int INF = 0x3f3f3f3f;
    const int MOD = 1000000007;
    
    char str[N];
    int dp[2][3300];
    //dp[i][j],表示到第i个字母为止,有j个属于第一个串
    
    int main ()
    {
    	int T, n;
    	scanf("%d", &T);
    	while (T --)
    	{
    		scanf("%d%s", &n, str);
    		memset(dp,0,sizeof(dp));
    		dp[0][0]=1;
    		for (int i=0,t=1; i<2*n; i++,t++)
            {
    			memset(dp[t&1],0,sizeof(dp[0]));
    			if (str[i]=='B')
    				for (int j=0;j<=n;j++)
    				{
    					if (j&1)  //奇数
    						dp[t&1][j+1] = (dp[t&1][j+1] + dp[i&1][j]) % MOD;
    					if ((i-j)&1)
    						dp[t&1][j] = (dp[t&1][j] + dp[i&1][j]) % MOD;
    				}
    			else
    				for (int j=0;j<=n;j++)
    				{
    					if ((j&1) == 0)
    						dp[t&1][j+1] = (dp[t&1][j+1] + dp[i&1][j]) % MOD;
    					if (((i-j)&1) == 0)
    						dp[t&1][j] = (dp[t&1][j] + dp[i&1][j]) % MOD;
    				}
    		}
    		printf("%d\n", dp[0][n]);
    	}
    	return 0;
    }

**FZU 2171 防守阵地 II**

线段树和树状数组都可以处理，和Hdu3468 （也有可能是POJ……）基本一样。神奇的是交C++过不了，交G++就过了……

#include <cstdio>
    #include <cstring>
    
    struct Node
    {
    	int left,right;
    	long long add,sum;
    }a[800005];
    
    int n,Q;
    
    void Build (int t,int left,int right)
    {
    	a[t].left=left;
    	a[t].right=right;
    	a[t].add=a[t].sum=0;
    	if (left==right)
    		return;
    	int mid=(left+right)>>1;
    	Build(t*2,left,mid);
    	Build(t*2+1,mid+1,right);
    }
    
    void Insert (int t,int target,int val)
    {
    	a[t].sum+=val;
    	if (a[t].left==target && a[t].right==target)
    		return;
    	int mid=(a[t].left+a[t].right)>>1;
    	if (target<=mid)
    		Insert(t*2,target,val);
    	else
    		Insert(t*2+1,target,val);
    }
    
    void Add (int t,int left,int right,int add)
    {
    	if (a[t].left==left && a[t].right==right)
    	{
    		a[t].add+=add;
    		return;
    	}
    	a[t].sum+=(right-left+1)*add;
    	int mid=(a[t].left+a[t].right)>>1;
    	if (right<=mid)
    		Add(t*2,left,right,add);
    	else if (left>mid)
    		Add(t*2+1,left,right,add);
    	else
    	{
    		Add(t*2,left,mid,add);
    		Add(t*2+1,mid+1,right,add);
    	}
    }
    
    long long Query (int t,int left,int right)
    {
    	if (a[t].left==left && a[t].right==right)
    		return a[t].sum+(a[t].right-a[t].left+1)*a[t].add;
    	int mid=(a[t].left+a[t].right)>>1;
    	Add (t*2,a[t].left,mid,a[t].add);
    	Add (t*2+1,mid+1,a[t].right,a[t].add);
    	a[t].sum+=(a[t].right-a[t].left+1)*a[t].add;
    	a[t].add=0;
    	if (right<=mid)
    		return Query(t*2,left,right);
    	else if (left>mid)
    		return Query(t*2+1,left,right);
    	else
    		return Query(t*2,left,mid)+Query(t*2+1,mid+1,right);
    }
    
    int main ()
    {
        int m;
        while (~scanf("%d%d%d",&n,&m,&Q))
        {
            memset(a,0,sizeof(a));
            Build (1,1,n);
            int i,L,R,x;
            for (i=1;i<=n;i++)
            {
                scanf("%d",&x);
                Insert(1,i,x);
            }
            for (i=1;i<=Q;i++)
            {
                scanf("%d",&L);
                R=L+m-1;
                printf("%lld\n",Query(1,L,R));
                Add(1,L,R,-1);
            }
        }
    	return 0;
    }

**Hdu 2173 Nostop**

这题算是组合数学中矩阵的一种应用吧，快速幂的新姿势，同时处理两个矩阵……看别人的代码貌似一个也行。

代码感觉写的还是有点挫的……刷点类似的题之后一起优化吧

#include <map>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define Upmin(a,b) ((a)=(a)<(b)?(a):(b))
    
    const int N=55;
    
    class Matrix
    {
    public:
    	bool a[N][N];  //保存是否可达
    	long long cost[N][N];   //保存最小花费
    	int n;   //矩阵大小
    
    	void init (int _n,int x)
    	{
    	    n=_n;
    		memset(a,false,sizeof(a));
    		if (x) for (int i=0;i<N;i++)
    		    a[i][i]=true;
            for (int i=0;i<N;i++)
                for (int j=0;j<N;j++)
                    cost[i][j]=((long long)1<<60);
        }
    
    	Matrix operator * (Matrix b)
    	{
    		Matrix p;
    		p.init(b.n,0);
    		for (int i=0;i<n;i++) for (int j=0;j<n;j++)
    		{
    		    for (int k=0;k<n;k++)
    			{
    			    if (a[i][k] && b.a[k][j])
    			    {
                        p.a[i][j]=true;
    			        Upmin(p.cost[i][j],cost[i][k]+b.cost[k][j]);
    			    }
    			}
    		}
    		return p;
    	}
    
    	Matrix power (int t)
    	{
    		Matrix ans,p=*this;
    		ans.init(p.n,1);
    		bool flag=false;
    		while (t)
    		{
    			if (t&1)
    			{
    			    if (flag==false) ans=p,flag=true;
    			    else ans=ans*p;
    			}
    			p=p*p;
    			t>>=1;
    		}
    		return ans;
    	}
    }a;
    
    int main ()
    {
        int T,n,h,k;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%d%d%d",&n,&h,&k);
            a.init (n,0);
            for (int i=0;i<h;i++)
            {
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                u--,v--;
                a.cost[u][v]=w;
                a.a[u][v]=true;
            }
            a=a.power(k);
            if (a.a[0][n-1]==false) puts("-1");
            else printf("%lld\n",a.cost[0][n-1]);
        }
    	return 0;
    }