完了，看来上一次的flag要应验了，我大概是真的要掉成pupil了吧。。
A - Connect Three
这个就是找到x的中间值，y的中间值，然后切一下，然后把所有的点挂到这条边上。但是我做的还是太慢了啊，还WA了一次，具体原因就是把(sort(x,x+3))写成了(sort(x,x+2))。。。然后就多花了十分钟。凉凉的前兆。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long ll;
const int Maxn=410000;
int x[10],y[10],a[10],b[10],num;
int ansx[Maxn],ansy[Maxn],bj[1100][1100];
int main() {
scanf("%d%d%d%d%d%d",&x[0],&y[0],&x[1],&y[1],&x[2],&y[2]);
memcpy(a,x,sizeof(a));
memcpy(b,y,sizeof(b));
sort(x,x+3);sort(y,y+3);
int xx=x[1],yy=y[1];
for(int i=x[0];i<=x[2];i++) bj[i][yy]=1;
for(int i=b[0];i<=yy;i++) bj[a[0]][i]=1;
for(int i=yy;i<=b[0];i++) bj[a[0]][i]=1;
for(int i=b[1];i<=yy;i++) bj[a[1]][i]=1;
for(int i=yy;i<=b[1];i++) bj[a[1]][i]=1;
for(int i=b[2];i<=yy;i++) bj[a[2]][i]=1;
for(int i=yy;i<=b[2];i++) bj[a[2]][i]=1;
for(int i=0;i<=1000;i++)
for(int j=0;j<=1000;j++)
if(bj[i][j]) ansx[++num]=i,ansy[num]=j;
printf("%d
",num);
for(int i=1;i<=num;i++)
printf("%d %d
",ansx[i],ansy[i]);
return 0;
}
B - Minimum Diameter Tree
这个有一个结论，最后有权值的边都是入度为1的点连出去的边，因为如果不是入度为1的点连出去的边，那么一定可以把他的权值下放给入度为1的边，这样一定不会更差。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long ll;
const int Maxn=410000;
int d[Maxn];
int main() {
int n,s,u,v;
scanf("%d%d",&n,&s);
for(int i=1;i<n;i++) {
scanf("%d%d",&u,&v);
d[u]++;d[v]++;
}
int sum=0;
for(int i=1;i<=n;i++)
if(d[i]==1) sum++;
printf("%.8lf",2.0*s/sum);
return 0;
}
C - Vasya and Templates
这个本质上是傻逼题，但是我太急了，所以就写崩了：
然后我考完试之后看了看数据，然后把一个很简单的特判改了一下就RE了，又一看是数组开小了，再改上就A了。。然而直接把这个特判删掉也能对。我。。。
好吧，这个题就是说如果a和b相等，那就直接挨着赋值，如果不行那就不行了。
如果不相等，那么从前往后看，如果这一位可以赋成两个中间的值，那剩下的随便赋就好了。
如果这一位那两个相等，那肯定要赋成这个值，如果不行那就不行了。
如果不相等，那就枚举赋成那个，另一个就不用考虑了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long ll;
const int Maxn=1010000;
int lens,k;
char s[Maxn],a[Maxn],b[Maxn];
int ans[31],vis[31],tmp[31],tmp2[31];
int sola(int x);
int solb(int x);
int main() {
// freopen("test.in","r",stdin);
int t;scanf("%d",&t);
while(t--) {
scanf("%d",&k);
scanf("%s%s%s",s,a,b);
memset(ans,-1,sizeof(ans));
memset(vis,-1,sizeof(vis));
lens=strlen(s);
int flag=0,bj=0;
for(int i=0;i<lens;i++) s[i]-='a',a[i]-='a',b[i]-='a';
for(int i=0;i<lens;i++)
if(b[i]<a[i]) {//对，没错，就是这个特判，我也是不知道怎么想的，还要判a是否小于b，但是他保证了这一点了吧。。
puts("NO");
bj=1;
break;
}
else if(b[i]>a[i]) break;
if(bj) continue;
for(int i=0;i<lens;i++)
if(a[i]!=b[i]) {
flag=1;
break;
}
if(flag) {
for(int i=0;i<lens;i++) {
if(~ans[s[i]]) {
if(ans[s[i]]>a[i]&&ans[s[i]]<b[i]) break;
if(ans[s[i]]<a[i]||ans[s[i]]>b[i]) {
puts("NO");
bj=1;break;
}
if(a[i]!=b[i]) {
if(ans[s[i]]==a[i]) if(sola(i+1)) break;
if(ans[s[i]]==b[i]) if(solb(i+1)) break;
puts("NO");
bj=1;
break;
}
}
else {
for(int j=a[i]+1;j<b[i];j++)
if(vis[j]==-1) {
ans[s[i]]=j;
vis[j]=s[i];
goto solve;
}
if(a[i]!=b[i]) {
memcpy(tmp,ans,sizeof(tmp));
memcpy(tmp2,vis,sizeof(tmp2));
if(vis[a[i]]==-1) {
ans[s[i]]=a[i],vis[a[i]]=s[i];
if(sola(i+1)) break;
}
memcpy(ans,tmp,sizeof(ans));
memcpy(vis,tmp2,sizeof(vis));
if(vis[b[i]]==-1) {
ans[s[i]]=b[i],vis[b[i]]=s[i];
if(solb(i+1)) break;
}
puts("NO");
bj=1;break;
}
else {
if(~vis[a[i]]) {
puts("NO");
bj=1;
break;
}
ans[s[i]]=a[i];
vis[a[i]]=s[i];
}
}
}
}
else {
for(int i=0;i<lens;i++)
if(ans[s[i]]==-1) {
if(vis[a[i]]==-1)
ans[s[i]]=a[i],vis[a[i]]=s[i];
else {
puts("NO");
bj=1;
break;
}
}
else
if(ans[s[i]]!=a[i]) {
puts("NO");
bj=1;
break;
}
}
solve:;
if(bj) continue;
int temp=0;
for(int i=0;i<k;i++) if(ans[i]==-1) {
while(~vis[temp]) temp++;
ans[i]=temp;vis[temp]=1;
}
puts("YES");
for(int i=0;i<k;i++) printf("%c",ans[i]+'a');
putchar('
');
}
return 0;
}
int sola(int x) {
for(int i=x;i<lens;i++) {
if(~ans[s[i]]) {
if(ans[s[i]]>a[i]) return 1;
if(ans[s[i]]<a[i]) return 0;
}
else {
for(int j=a[i]+1;j<k;j++) if(vis[j]==-1) {
ans[s[i]]=j;
vis[j]=s[i];
return 1;
}
if(vis[a[i]]==-1) {
ans[s[i]]=a[i];
vis[a[i]]=s[i];
continue;
}
return 0;
}
}
return 1;
}
int solb(int x) {
for(int i=x;i<lens;i++) {
if(~ans[s[i]]) {
if(ans[s[i]]<b[i]) return 1;
if(ans[s[i]]>b[i]) return 0;
}
else {
for(int j=0;j<b[i];j++) if(vis[j]==-1) {
ans[s[i]]=j;
vis[j]=s[i];
return 1;
}
if(vis[b[i]]==-1) {
ans[s[i]]=b[i];
vis[b[i]]=s[i];
continue;
}
return 0;
}
}
return 1;
}
这场也体现出了一些缺陷，比如看题太过急躁，代码能力还是较弱，调试能力太差，做题状态不佳，这些可能是与平常练习的方式有关，最近要努力了，争取能再上回去，当然能上橙更好啊。