T1 小Z切课本(cut)

Description

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

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

Input

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

Output

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

Sample Input

6 4 2

Sample Output

8

Hint

Subtask1 (20 points) 满足 (n,m leq 10)

Subtask2 (20 points) 满足(n,m leq 5000)

Subtask3 (20 points) 满足(n,m leq 10^7)

Subtask4 (40 points) 满足(n,m leq 10^9)

Solution

可以简单的证明出，如果切割次数允许只在同一个方向切，肯定是最优的，

否则，肯定是将长边切满之后再切短边最优，因此只需要使得切的边最小的尽可能大，所以要尽量等分，最后计算一下答案就好了。

时空复杂度均为(O(1))

Code

#include <stdio.h>
#define R register
#define ll long long
#define AK_titoly ditoly
#define max(a,b) ((a)>(b)?(a):(b))
#define file(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
inline int read(){
	R int x; R bool f; R char c;
	for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');
	for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');
	return f?-x:x;
}
int n,m,k;
int main(){
	file(cut);
	n=read(),m=read(),k=read();
	if (k-n-m+2>0) return 0*puts("-1");
	if (n>m) n^=m,m^=n,n^=m;
	if (k>=m) printf("%d
",n/(k-m+2));
	else printf("%lld
",max(1ll*n*(m/(k+1)),1ll*m*(n/(k+1))));
	return 0;
}

T2 小Z爱数组(array)

Description

小Z最喜欢数组了，现在他得到了由n个正整数组成的数组ai，他想构造一个相同大小的正整数数组bi满足两个数组的差异度(Sigma |ai -bi|)最小。特殊的是，bi数组的所有元素必须满足两两互质。

Input

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

接下来一行n个正整数ai，表示给定的数组。

Output

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

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

Sample Input

5

1 6 4 2 8

Sample Output

1 5 4 1 9

Hint

Subtask1 (20points) 满足$ n leq 8 , 1 leq ai leq 5$

Subtask2 (30points) 满足$ n leq 50 , 1 leq ai leq 15$

Subtask3 (50points) 满足$ n leq 100 , 1 leq ai leq 30$

Solution

容易发现(1 leq bi leq 58)，如果(bi>58) 可以证明用1替代是等价或更优的，显然，58以内的所有质数只能在整个序列中作为最多一个数的质因子出现，经计算的，58以内的质数个数为16个，故所有质数的状态只有(2^{16})种情况,考虑状态压缩，预处理出1～58中每个数所拥有的质因子集合，使用状态压缩DP即可通过。状态转移方程为：$$f[i][S|set[j]]=f[i-1][S]+|ai-j|(1 leq j leq 58 vee set[j]cap S = phi )$$

其中(set[j])表示j含有的质因数集合,(f[i][S])表示前i个位置，质因数状态为S的最优答案。

总复杂度为(O(58n*2^{16})/O(n*2^{16}))。

Code

#include <stdio.h>
#include <string.h>
#define R register
#define MN 105
#define inf 0x3f3f3f3f
#define AK_titoly ditoly
#define file(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
inline int read(){
	R int x; R bool f; R char c;
	for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');
	for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');
	return f?-x:x;
}
inline int abs(int x){return x<0?-x:x;}
int a[MN],f[MN][1<<16],pre[MN][1<<16],set[MN],n,pn,ans=0,b[MN];
bool ud[MN];
void init(){
	for (R int i=2; i<59; ++i)
		if (!ud[i]){
			for (R int j=1; j<=58/i; ++j){
				ud[i*j]=1;
				set[i*j]|=(1<<pn);
			}++pn;
		}
}
int main(){
	file(array);init();n=read();
	for (R int i=1; i<=n; ++i) a[i]=read();
	memset(f,0x3f,sizeof(f));
	for (R int S=0; S<(1<<16); ++S) f[0][S]=0;
	for (R int i=1; i<=n; ++i)
		for (R int j=1; j<59; ++j)
			for (R int S=0; S<(1<<16); ++S)
				if (!(set[j]&S)&&f[i][S|set[j]]>f[i-1][S]+abs(j-a[i]))
					f[i][S|set[j]]=f[i-1][S]+abs(j-a[i]),pre[i][S|set[j]]=j;
	for (R int S=1; S<(1<<16); ++S) if (f[n][ans]>f[n][S]) ans=S;
	for (R int i=n; i; --i) b[i]=pre[i][ans],ans^=set[pre[i][ans]];
	for (R int i=1; i<=n; ++i) printf("%d ",b[i]);
	return 0;
}

T3 小Z爱修路(road)

Description

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

Input

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

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

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

Output

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

Sample Input

3 2 2

1 2 1

2 3 1

2 2

3 1

Sample Output

1

Hint

对于20%的数据,满足(n,m,k leq 100);

另有20%的数据,满足(k leq 4)

对于100%的数据,满足(n,k leq 50000 , m leq 200000 , 1 leq ti,wi leq 10^9 si geq 2)

Solution

考虑一条新建的边一定会被修建的原因，显然是因为2个原因：

1.从1号点到这条边的另一端的最短路被修改了

2.最短路一定包含新的修建的边

考虑如何维护上述两种情况，显然，只需要求一次原先的最短路，然后求一下现今的最短路，维护新最短路的前驱，并且判断多条最短路时，前驱优先选择非1号点的即可，事实上，由于我们在跑最短路时，1号点只会在开始时更新1次，故只需要在最短路更新或相等时，修改前驱即可。

总复杂度为$O((m+k) log n) / O(n+m+k) $

Code

#include <stdio.h>
#include <string.h>
#define MN 50005
#define MM 200005
#define M (1<<16)
#define R register
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3fll
#define AK_titoly ditoly
#define file(f) freopen(#f".in","r",stdin);freopen(#f".out","w",stdout);
inline int read(){
	R int x; R bool f; R char c;
	for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');
	for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');
	return f?-x:x;
}
inline int min(R int a,R int b){return a<b?a:b;}
struct node{ll v;int pos;}T[M<<1];
int to[MM+MN<<1],nxt[MM+MN<<1],v[MM+MN<<1],h[MN],pre[MN],n,m,k,en,ans;
ll dis[MN],dis2[MN];
inline void ins(int x,int y,int vl){to[++en]=y,nxt[en]=h[x],v[en]=vl,h[x]=en;}
inline node min(node a,node b){return a.v<b.v?a:b;}
inline void A(int k,ll v){for (T[k+=M].v=v; k>>=1; T[k]=min(T[k<<1],T[k<<1|1]));}
inline void dij(int u,ll *dis){
	memset(pre,0,sizeof(pre));
	memset(T,0x3f,sizeof(T));for (R int i=1; i<=n; ++i) T[i+M].pos=i;
	A(u,0);dis[u]=0;for (R int i=1; i<=n; ++i){
		u=T[1].pos;A(u,INF);for (R int j=h[u]; j; j=nxt[j]){
			if (dis[to[j]]>=dis[u]+v[j]) pre[to[j]]=u;
			if (dis[to[j]]>dis[u]+v[j]) A(to[j],dis[to[j]]=dis[u]+v[j]);
		}
	}
}
int main(){
	file(road);
	memset(dis,0x3f,sizeof(dis));
	memset(dis2,0x3f,sizeof(dis));
	n=read(),m=read(),k=read();
	for (R int i=1; i<=m; ++i){
		R int x=read(),y=read(),v=read();
		ins(x,y,v);ins(y,x,v);
	}dij(1,dis);for (R int i=1; i<=k; ++i){
		R int x=1,y=read(),v=read();
		ins(x,y,v);ins(y,x,v);
	}dij(1,dis2);for (R int i=2; i<=n; ++i)
		if (dis2[i]<dis[i]&&pre[i]==1) ++ans;
	printf("%d
",k-ans);
	return 0;
}