1001
1002
比赛的时候没看懂题。看完题解依旧WA好久。 偷看数据发现坑多。不容易考虑全。
假设m>=n，否则转置一下。 下面所描述的left，right，up，down全部和官方题解相同。
要注意。left，right与up，down在图上的取法是不一样的。
首先考虑无坏点的情况。取ans=n/2+1必然能覆盖整个图。此时全部纵向铺条。
如图所示为n=4，m=5的情况。
加上坏点后。要分两类讨论。
i) 当min（left，right）<=ans时。不妨设left<ans。
那么只要坏点左边（包含坏点）横向铺条。右边纵向铺条。一定能铺满。
此时我们有两种方案（不妨设ans<left<=right）
1)在坏点左边（包含坏点）用 left长度横铺，右边（不包含坏点）纵铺。（因为left>ans。这是必然可行的。）2)用max(up,down) 长度全部纵铺。那么在1)与2)中选择更优的即为答案。
最后一个坑。边长为奇数的方形且坏点在中间。答案为ans-1。
1 # include2 # include 3 # include 4 using namespace std; 5 6 int main(void) 7 { 8 int n,m,x,y; 9 while((scanf("%d%d%d%d",&n,&m,&x,&y))!=EOF)10 {11 if(n>m) {swap(n,m); swap(x,y);}12 int ans=(n+1)/2;13 int left=y,right=m-y+1,up=x-1,down=n-x;14 if(min(left,right)>ans&&max(up,down)-min(up,down)>1)15 ans=min(min(left,right),max(up,down));16 if(n%2&&m==n&&left==right&&up==down) ans--;17 printf("%d\n",ans);18 }19 return 0;20 }
1003
1004
苹果数最多为1e5。所以把每个苹果看成一个点。
按中线将苹果分成左右两边。用dist表示每个苹果的距离。
cnt计两边苹果数。全部读好sort一遍。
先考虑贪心的取两边的苹果。
sum[i]表示在某一边取完1-i的苹果回去后走的最小路程。
递推sum数组直到sum[cnt]。
转移方程是i<=k时sum[i]=2*dist[i],i>k时sum[i]=sum[i-k]+2*dist[i]。
这样的话得到一个ans=suml[cntl]+sumr[cntr]。
然而会发现。如果贪心到最后在一边取的苹果不到k个。那么会存在走一圈更优的情况。
但是走一圈最多只有一次。因为如果多于一次就能拆成两个小于半圈的。必然小于一圈。
那么我们可以枚举走一圈的时候。分别在左半右半取了多少个。
例如左半取i个右半取k-i个。那么这i个一定要取左半距离最大的。右半同理。
这里要注意枚举时，枚举的个数不能超过左边和右边的总个数。
最后注意LL。
1 # include2 # include 3 # include 4 using namespace std; 5 typedef long long LL; 6 # define maxn 100010 7 int distl[maxn],distr[maxn]; 8 LL suml[maxn]={ 0},sumr[maxn]={ 0}; 9 10 int main(void)11 {12 int T; cin>>T;13 while(T--)14 {15 LL L; int n,k;16 scanf("%I64d%d%d",&L,&n,&k);17 int cntl=0,cntr=0;18 for(int i=1;i<=n;i++)19 {20 int x,a; scanf("%d%d",&x,&a);21 for(int j=0;j
1005
1006
连个暴搜都写不出来。不开心。
官方题解说搜点。加上两点优化：1.只考虑偶数边 2.最后一条边由前面的边确定。
在网上找到了简单易懂的做法。跑的不是很快是超级快。
先读边。每个点记下度数。如果有奇数的就直接输0过了。
所有点的度都是偶数的情况下。每个节点的on边与off边是相等的，即为度数一半。
直接搜边。枚举每条边分别是on边与off边的情况。
如果过程中有点的on边或者off边举完了。边还没搜完。
那么该情况就是不可行的。直接return。
1 # include2 # include 3 # include 4 using namespace std; 5 # define CLR(x) memset(x,0,sizeof(x)) 6 int ans,m,n,deg[10],on[10],off[10]; 7 8 struct E 9 {10 int from,to;11 } edge[30];12 13 void dfs(int x)14 {15 if(x>m) {ans++; return;}16 int u=edge[x].from,v=edge[x].to;17 if(on[u]&&on[v])18 {19 on[u]--; on[v]--;20 dfs(x+1);21 on[u]++; on[v]++;22 }23 if(off[u]&&off[v])24 {25 off[u]--; off[v]--;26 dfs(x+1);27 off[u]++; off[v]++;28 }29 return;30 }31 32 int main(void)33 {34 int T; cin>>T;35 while(T--)36 {37 CLR(edge); CLR(deg); CLR(on); CLR(off);38 scanf("%d%d",&n,&m);39 for(int i=1;i<=m;i++)40 {41 int u,v; scanf("%d%d",&u,&v);42 edge[i].from=u; edge[i].to=v;43 deg[u]++; deg[v]++;44 }45 int ok=1;46 for(int i=1;i<=n;i++) if(deg[i]%2) {ok=0; break;}47 if(!ok) {printf("0\n"); continue;}48 for(int i=1;i<=n;i++) on[i]=off[i]=deg[i]/2;49 ans=0; dfs(1);50 printf("%d\n",ans);51 }52 return 0;53 }
1007
1008
1009
没什么技术含量。看官方题解。
只要能推出所有的情况就好。
然而把式子全部变成代码也挺不容易的。
一处WA整个都要重新检查一次。过的时候真的感动哭。
【第一次遇见说代码太长的情况。也有可能是HDU或者我网炸。】
1 # include2 # include 3 using namespace std; 4 5 int main(void) 6 { 7 int n; 8 while((scanf("%d",&n))!=EOF) 9 {10 if(n<4) printf("-1\n");11 if(n==4) printf("1 * 2\n5 + 3\n6 + 4\n");12 if(n==5) printf("1 / 2\n6 / 3\n4 - 7\n5 * 8\n");13 if(n==6) printf("1 + 2\n3 + 7\n4 + 8\n5 + 9\n10 - 6\n");14 if(n==7) printf("1 * 2\n3 / 4\n5 + 6\n8 - 9\n11 / 10\n12 * 7\n");15 if(n==8) 16 {17 printf("1 + 2\n9 + 3\n4 - 5\n11 * 6\n");18 printf("12 * 7\n13 * 8\n14 + 10\n");19 }20 if(n==9)21 {22 printf("1 + 2\n10 + 3\n4 / 5\n6 / 7\n");23 printf("8 / 9\n11 - 12\n15 - 13\n16 - 14\n");24 }25 if(n==10)26 {27 printf("1 / 2\n3 / 4\n5 / 6\n7 / 8\n9 + 10\n");28 printf("11 + 12\n16 + 13\n17 + 14\n18 + 15\n");29 }30 if(n==11)31 {32 printf("1 + 2\n3 / 4\n5 / 6\n12 + 13\n15 + 14\n");33 printf("7 - 8\n17 * 9\n18 * 10\n19 * 11\n20 + 16\n");34 }35 if(n==12)36 {37 printf("1 - 2\n");38 for(int i=0;i<8;i++) printf("%d * %d\n",i+3,i+13);39 printf("11 + 12\n21 + 22\n");40 }41 if(n==13)42 {43 printf("1 / 2\n3 - 14\n4 + 5\n16 / 6\n15 * 17\n7 - 8\n");44 for(int i=0;i<5;i++) printf("%d * %d\n",i+9,i+19);45 printf("24 + 18\n");46 }47 if(n==14)48 {49 printf("1 / 2\n3 / 4\n5 - 15\n17 - 16\n6 + 7\n19 / 8\n20 * 18\n9 - 10\n");50 for(int i=0;i<4;i++) printf("%d * %d\n",i+11,i+22);51 printf("21 + 26\n");52 }53 if(n>14)54 {55 printf("1 + 2\n3 + 4\n5 + 6\n7 + 8\n%d + 9\n",n+1);56 for(int i=0;i<4;i++) printf("%d / %d\n",n+2+i,i+10);57 printf("14 - 15\n");58 for(int i=0;i
1010