补卡...

12.25：最小生成树

题目链接：22NYIST最小生成树专题 [Cloned] - Virtual Judge (vjudge.net)

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
typedef long long ll;
using namespace std;
int f[10005];
struct node 
{int a, b;int w;
}p[10005];
bool cmp(node x , node y)
{return x.w < y.w;
}
int find(int x){if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
int main(){int y;while(~scanf("%d",&y)){if(y==0) break;int n;int sum=0;n=y*(y-1)/2;int cnt=0;while(n--){scanf("%d %d %d",&p[cnt].a,&p[cnt].b,&p[cnt].w);cnt++;}sort(p,p+cnt,cmp);for(int i=1;i<=y;i++)f[i]=i;for(int i=0;i<cnt;i++){int a = p[i].a , b =p[i].b , w = p[i].w;a = find(a);b = find(b);if(a==b) continue;else{f[a]=b;sum+=w;}}cout<<sum<<endl;;}
}

12.26

现在基本上熟悉板子题了

题目链接：22NYIST最小生成树专题 [Cloned] - Virtual Judge (vjudge.net)

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
typedef long long ll;
using namespace std;
int f[10005];
struct node{int a,b;double d;
}p[10005];
int find(int x){if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
int cmp(node x,node y){return x.d<y.d;
}
double x[105],y[105];
int main(){int n;int t;cin>>t;while(t--){cin>>n;int cnt=0;for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=n;i++) cin>>x[i]>>y[i];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) continue;p[cnt].a=i;p[cnt].b=j;p[cnt].d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));if(p[cnt].d>1000||p[cnt].d<10) cnt--;cnt++;}}sort(p,p+cnt,cmp);double sum=0;for(int i=0;i<cnt;i++){int a=find(p[i].a),b=find(p[i].b);if(a==b) continue;else {f[a]=b;sum+=p[i].d;}}int p=0;for(int i=1;i<n;i++){if(find(i)!=find(i+1))p++;}if(p!=0) cout<<"oh!"<<endl;else printf("%.1f\n",sum*100);}
}

12.27

周赛的折线分割面

题目链接：NYIST集训队 12.24周赛 - Virtual Judge (vjudge.net)

整体思路：先推导一根线的公式，然后一个折线就相当于两根直线只不过三个面变成一个面，然后推导出公式：f(n) = ((1 + n) * n / 2) + 1 - 2 * n  =  2 * n * n - n + 1。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
typedef long long ll;
using namespace std;
int main(){int t,n;cin>>t;while(t--){cin>>n;cout<<2*n*n-n+1<<endl;}
}

12.28

周赛b题

题目链接：NYIST集训队 12.24周赛 - Virtual Judge (vjudge.net)

整体思路：就是找到先标记然后，先到两个标记的就是可以保存的，然后其他就要删除。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
typedef long long ll;
using namespace std;
int t[105];
int main(){ll t1;cin>>t1;while(t1--){ll len,sum=0;memset(t,0,sizeof(t));string a;cin>>a;len=a.length();for(int i=0;i<len;i++){if(t[a[i]-'a']==1){memset(t,0,sizeof(t));sum+=2;}else {t[a[i]-'a']=1;}}cout<<len-sum<<endl;}
}

补卡...

12.25：最小生成树

题目链接：22NYIST最小生成树专题 [Cloned] - Virtual Judge (vjudge.net)

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
typedef long long ll;
using namespace std;
int f[10005];
struct node 
{int a, b;int w;
}p[10005];
bool cmp(node x , node y)
{return x.w < y.w;
}
int find(int x){if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
int main(){int y;while(~scanf("%d",&y)){if(y==0) break;int n;int sum=0;n=y*(y-1)/2;int cnt=0;while(n--){scanf("%d %d %d",&p[cnt].a,&p[cnt].b,&p[cnt].w);cnt++;}sort(p,p+cnt,cmp);for(int i=1;i<=y;i++)f[i]=i;for(int i=0;i<cnt;i++){int a = p[i].a , b =p[i].b , w = p[i].w;a = find(a);b = find(b);if(a==b) continue;else{f[a]=b;sum+=w;}}cout<<sum<<endl;;}
}

12.26

现在基本上熟悉板子题了

题目链接：22NYIST最小生成树专题 [Cloned] - Virtual Judge (vjudge.net)

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
typedef long long ll;
using namespace std;
int f[10005];
struct node{int a,b;double d;
}p[10005];
int find(int x){if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
int cmp(node x,node y){return x.d<y.d;
}
double x[105],y[105];
int main(){int n;int t;cin>>t;while(t--){cin>>n;int cnt=0;for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=n;i++) cin>>x[i]>>y[i];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) continue;p[cnt].a=i;p[cnt].b=j;p[cnt].d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));if(p[cnt].d>1000||p[cnt].d<10) cnt--;cnt++;}}sort(p,p+cnt,cmp);double sum=0;for(int i=0;i<cnt;i++){int a=find(p[i].a),b=find(p[i].b);if(a==b) continue;else {f[a]=b;sum+=p[i].d;}}int p=0;for(int i=1;i<n;i++){if(find(i)!=find(i+1))p++;}if(p!=0) cout<<"oh!"<<endl;else printf("%.1f\n",sum*100);}
}

12.27

周赛的折线分割面

题目链接：NYIST集训队 12.24周赛 - Virtual Judge (vjudge.net)

整体思路：先推导一根线的公式，然后一个折线就相当于两根直线只不过三个面变成一个面，然后推导出公式：f(n) = ((1 + n) * n / 2) + 1 - 2 * n  =  2 * n * n - n + 1。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
typedef long long ll;
using namespace std;
int main(){int t,n;cin>>t;while(t--){cin>>n;cout<<2*n*n-n+1<<endl;}
}

12.28

周赛b题

题目链接：NYIST集训队 12.24周赛 - Virtual Judge (vjudge.net)

整体思路：就是找到先标记然后，先到两个标记的就是可以保存的，然后其他就要删除。

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
typedef long long ll;
using namespace std;
int t[105];
int main(){ll t1;cin>>t1;while(t1--){ll len,sum=0;memset(t,0,sizeof(t));string a;cin>>a;len=a.length();for(int i=0;i<len;i++){if(t[a[i]-'a']==1){memset(t,0,sizeof(t));sum+=2;}else {t[a[i]-'a']=1;}}cout<<len-sum<<endl;}
}