这次比赛由学长出题，欢迎去他的blog学习！

【T1】切课本

题意：

小 Z 厌恶数学，他决定将数学课本切成一块一块的。他的课本是一个 n*m 的矩形，小 Z 决定切 K 刀，每刀他可以横着切或者竖着切，但是切成的矩形的长和宽都必须是整数。当然，小 Z 不会做出两次相同的操作。例如 n=6,m=4,k=3 时，以下是一种合法的切法。

不巧的是，小 Z 的数学老师知道了他这个行为，并且刁钻的老师肯定会找到切出的矩形中面积最小的那一块来 D 他， 所以小 Z 想知道最优情况下面积最小的那一块面积最大能是多少？

输入：

输入数据只包含一行三个整数 n,m,k，含义如题目所述。

输出：

输出一个数字，表示答案。 如果没有合法的方案，输出-1。

题解：

固定一个方向的刀数的时候，肯定是尽量平均切。

如果能只切一边的话，只切一边一定最优。

假设 n<=m， k>=m 时，考虑将一边全部切开，剩下的平均切到另一边。

长的边切 m-1 刀，另一边切 k-(m-1)刀一定最优，因为， n/(k-(n-1))>=m/(k-(m-1))。

1 #include
     
       2 #include
      
        3 using namespace std; 4 inline int read() 5 { 6     int x=0,f=1;char ch=getchar(); 7     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();} 8     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 9     return x*f;10 }11 int n,m,k;long long ans=0;12 int main()13 {14     freopen("cut.in","r",stdin);15     freopen("cut.out","w",stdout);16     n=read();m=read();k=read();17     if(n+m-2
       
        =i) ans=max(ans,1LL*(n/j)*(m/(k-(j-1)+1)));22     }23     printf("%lld\n",ans);24     return 0;25 }
       
      
     

【T2】海棠数组

题意：

小 Z 最喜欢数组了，现在他得到了由 n 个正整数组成的数组 ai。

他想构造一个相同大小的正整数数组 bi 满足两个数组的差异度\(\sum_{i=1}^{n}|a_{i}-b_{i}|\)最小。

特殊的是， bi 数组的所有元素必须满足两两互质。

输入：

第一行一个数 n， 表示数组大小。

接下来一行 n 个正整数 ai， 表示给定的数组。(1<=ai<=30)

输出：

输出一行 n 个正整数 bi，表示答案。

输出的数字必须满足 1<=bi<=10^9。如果有多个答案，你可以输出任意一个。

题解：

ai<=30，那么，如果选取的bi大于58，可以换成1，而答案不会更劣。

所以1<=bi<=58，再考虑互质的条件，说白了就是质因数不能重复，而58以内的质数只有16个，故使用状压DP。

用 f[i][j] 表示前 i 个数中，选取了集合 j 中的质数。用 fcts[i] 表示 i 的质因子集合。

有 f[i][j]=min( f[i-1][j\fcts[k]] + |ai-k| )。其中k取遍1到58。预处理出fcts加快速度。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #define ll long long 8 #define mem(qaq,x) memset(qaq,x,sizeof(qaq)) 9 #define For(i,a,b) for (int i=a; i<=b; i++)10 #define Ford(i,a,b) for (int i=a; i>=b; i--)11 #define File(fn) freopen(fn".in","r",stdin);freopen(fn".out","w",stdout);12 using namespace std;13 14 const int fcts[59]={ 0,0,1,2,1,4,3,8,1,2,5,16,3,32,9,6,1,64,3,128,5,10,17,256,3,4,33,2,9,512,7,1024,1,18,65,12,3,2048,129,34,5,4096,11,8192,17,6,257,16384,3,8,5,66,33,32768,3,20,9,130,513};15 int n,a[101],f[101][65536];16 short g[101][65536],ans[101];17 18 inline int Abs(int x){ return x<0?-x:x;}19 20 void init(){21 scanf("%d",&n);22 For(i,1,n) scanf("%d",a+i);23 }24 25 void dp(){26 memset(f,0x3f,sizeof f);27 f[0][0]=0;28 For(i,1,n){29 For(j,0,65535){30 For(k,1,58){31 if((fcts[k]&j)!=fcts[k]) continue;32 if(f[i][j]>f[i-1][j^fcts[k]]+Abs(a[i]-k)){33 f[i][j]=f[i-1][j^fcts[k]]+Abs(a[i]-k);34 g[i][j]=k;35 }36 }37 }38 }39 }40 41 int main(){42 File("array");43 init();44 dp();45 int x=-1, y=-1, s=99999999;46 For(j,0,65535) if(f[n][j]
          
         
        
       
      
     

【T3】修路

题意：

L 国包含 n 个城市和 m 条双向道路，第 i 条道路连接 ui,vi 两个城市， 距离为ti，这些道路将所有 n 个城市连接在一起。 明年， L 国将会在首都，也就是 1 号城市举办一年一度的 NOI，所以 L 国的国王委托小 Z 新建一些道路来减少一些城市到达首都的距离。小 Z 很快修好了道路，但是他却不是很满意。他想知道最多可以少新建多少道路，满足首都到所有城市的最短路长度和现在相同。

输入：

第一行读入三个数字 n,m,k，依次表示城市的数量，原有道路的数量和新建道路的数量。

接下来 m 行，每行三个数字 ui,vi,ti，表示一条原有的道路

最后 k 行，每行两个数字 si,wi，表示一条新建的道路连接 1 和 si，距离为 wi。

输出：

输出一个整数，表示最多能少修建多少条新建的道路 。

题解：

把所有新加的边去个重，到相同的点的边只保留一个最小的，然后跑一次最短路。

一条新加的边如果长度不是最短路一定可以去掉，否则只有满足有其它最短路径到达这个点的时候才可以去掉。

算出到每个点最短路条数是否大等于 2 即可。

复杂度 O((n+k)logn)

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #define ll long long 9 #define mem(qaq,x) memset(qaq,x,sizeof(qaq))10 #define For(i,a,b) for (int i=a; i<=b; i++)11 #define Ford(i,a,b) for (int i=a; i>=b; i--)12 #define File(fn) freopen(fn".in","r",stdin);freopen(fn".out","w",stdout);13 using namespace std;14 15 inline int in(){16 int x=0,f=1;17 char ch=getchar();18 while (ch<'0'||ch>'9')f=ch=='-'?0:1,ch=getchar();19 while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();20 return f?x:-x;21 }22 23 typedef pair
            
              P;24 25 int n,m,k,ans;26 int h[50001],nxt[500001],to[500001],w[500001],tot=0;27 inline void ins(int x,int y,int z){nxt[++tot]=h[x];to[tot]=y;w[tot]=z;h[x]=tot;}28 int dis[50001],num[50001];29 int kkkk[50001];30 priority_queue
             
              
,greater
              
 > pq;31 32 void init(){33 int x,y,z;34 n=in(); m=in(); k=in();35 For(i,1,m){36 x=in(), y=in(), z=in();37 ins(x,y,z);38 ins(y,x,z);39 }40 For(i,1,k){41 int y=in(), z=in();42 if(!kkkk[y]) kkkk[y]=z;43 else ++ans,kkkk[y]=std::min(kkkk[y],z);44 }45 For(i,1,n) if(kkkk[i]) ins(1,i,kkkk[i]), ins(i,1,kkkk[i]);46 }47 48 void dij(){49 memset(dis,0x3f,sizeof dis);50 dis[1]=0; pq.push(P(0,1));51 num[1]=1;52 while(!pq.empty()){53 P u=pq.top(); pq.pop();54 if(u.first>dis[u.second]) continue;55 for(int i=h[u.second];i;i=nxt[i]){56 if(dis[u.second]+w[i]
               
                dis[i]) ++ans;74 if(kkkk[i]==dis[i]&&num[i]>1) ++ans;75 }76 printf("%d",ans);77 return 0;78 }