=-=昨天被老师拉去吃点心了就没有发题解...忧伤..昨天的T2貌似都没有调完嗯
今天脑洞是大啊..
T1模拟写挂..呵呵我一面
T2数学题..刚开始只会求素数表的那种方法暴力..不过后面他们都知道一种数学方法..然后算是A了吧
T3SPFA..不过感觉略复杂..不会啊QAQ
T4最大生成树啊...没有时间打了 喜闻乐见，不过感觉还是会有一个地方卡住，详见题解
T1：纯模拟
像我这样代码能力那么弱的人，就很容易写挂了
就比如
h=s+n-1;
while(h>m){
h-=m;
}
要判断第一个点有没有超范围..之后的点虽然有想到，不过第一个点你想到了没有！
...有空多练练这种无脑题吧...再写挂就不好玩了嗯
附上代码：
#include<cstdio>
#include<cstring>
using namespace std;
int h,m,s,n,k,ans=0,tot=0;
bool a[1001];
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d%d%d%d",&m,&s,&n,&k);
memset(a,true,sizeof(a));
h=s+n-1;
while(h>m){
h-=m;
}
a[h]=false;
printf("%d ",h);
for(int i=2;i<=m;i++){
if(i%2==0){
for(int j=1;j<=k;j++){
h--;
if(h==0) h=m;
if(!a[h]){
while(!a[h]){
h--;
if(h==0) h=m;
}
}
}
}
a[h]=false;
if(i%2!=0){
for(int j=1;j<=n;j++){
h++;
if(h==m+1) h=1;
if(!a[h]){
while(!a[h]){
h++;
if(h==m+1) h=1;
}
}
}
a[h]=false;
}
printf("%d ",h);
}
return 0;
}
T2：数论..
这块内容还是不太懂的..主要是多积累，如果有遇上的话就很好解决了
=-=不太懂这题的原理...忧伤
#include<cstdio>
#include<cstring>
using namespace std;
int tot=0,ans=0;
int n,m;
int f[10000001];
int main(){
freopen("shlqsh.in","r",stdin);
freopen("shlqsh.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
tot+=m/i;
for(int i=1;i<=n-1;i++)
ans+=(n-1)/i;
printf("%d",tot-ans);
return 0;
}
T4：最大生成树
先说说T4好了...毕竟T3没有改..不懂怎么说
T4算是很裸的最大生成树了
就是有一个地方需要注意，就是给男生编号这个地方
你想啊...你需要区别男生女生对吧..男生就在女生后面往下编就可以
还有打了这题，除了对最大生成树复习之外，貌似对最后一步的加边操作有了更深的理解了吧，if(k==n+m-1) break;
嗯。。顺便回顾一下最大生成树的内容：
1.存边f[i].a,f[i].b,f[i].c
2.排序（根据是求最大生成树还是最小生成树来定..），感觉有时也需要看题目,PS:顺便注意一下一个struct排序时的用法
struct qem{
int a,b,z;
}f[200001];
int cmp(qem f,qem b){
return f.z>b.z;
}
3.加边，直到构成一颗树为止
这一步需要用来并查集，来判断是否有共同的祖先，进行n-1的加边操作即可
附上代码..
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,r,h,t,ans=0;
int x,y,z,tot=0,maxn;
struct qem{
int a,b,z;
}f[200001];
int cmp(qem f,qem b){
return f.z>b.z;
}
int fa[200001];
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
int main(){
freopen("conscription.in","r",stdin);
freopen("conscription.out","w",stdout);
scanf("%d%d%d",&n,&m,&r);
for(int i=1;i<=r;i++){
scanf("%d%d%d",&x,&y,&z);
y+=n;
f[i].a=x;
f[i].b=y;
f[i].z=z;
}
for(int i=0;i<=n+m;i++) fa[i]=i;
sort(f+1,f+r+1,cmp);
int k=0;
for(int i=1;i<=r;i++){
h=find(f[i].a);
t=find(f[i].b);
if(h!=t){
fa[h]=t;
ans+=f[i].z;
++k;
}
if(k==n+m-1) break;
}
tot=10000*(m+n)-ans;
printf("%d",tot);
return 0;
}
T3：spfa
不是太明白怎么打..
附上标程吧..
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
#define fi first
#define se second
using namespace std;
const int inf=2000000000;
typedef pair<int,int> pii;
vector<pii> a[10010];
priority_queue<pii> q;
int g[110][110],d[10010],p[10010],ans[10010];
bool f[10010];
pii v[10010];
int main(){
int n,s,t,nn,mm,i,j,x,y,sx,sy,tx,ty;
vector<pii>::iterator it;
freopen("kingdom.in","r",stdin);
freopen("kingdom.out","w",stdout);
scanf("%d%d%d%d%d%d",&nn,&mm,&sx,&sy,&tx,&ty);
memset(g,0,sizeof(g));
for (i=1;i<=mm;i++){
scanf("%d%d",&x,&y);
g[x][y]=g[y][x]=1;
}
n=0;
for (i=1;i<nn;i++)
for (j=i+1;j<=nn;j++)
if (g[i][j]){
v[++n].fi=i;v[n].se=j;
if (sx==i && sy==j) s=n;
if (tx==i && ty==j) t=n;
v[++n].fi=j;v[n].se=i;
if (sx==j && sy==i) s=n;
if (tx==j && ty==i) t=n;
}
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
if (v[i].fi!=v[j].se || v[i].se!=v[j].fi)
if (v[i].fi==v[j].fi){
if (g[v[i].se][v[j].se]){
a[i].push_back(make_pair(j,1));
a[j].push_back(make_pair(i,1));
}
}
else
if (v[i].se==v[j].se){
if (g[v[i].fi][v[j].fi]){
a[i].push_back(make_pair(j,1));
a[j].push_back(make_pair(i,1));
}
}
else
if (g[v[i].fi][v[j].fi] && g[v[i].se][v[j].se]){
a[i].push_back(make_pair(j,2));
a[j].push_back(make_pair(i,2));
}
for (i=1;i<=n;i++){
d[i]=inf;p[i]=0;f[i]=false;
}
d[s]=0;q.push(make_pair(0,s));
for (i=1;i<=n;i++){
while (f[x=q.top().se]) q.pop();
q.pop();
if (x==t) break;
f[x]=true;
for (it=a[x].begin();it!=a[x].end();it++){
y=it->fi;
if (!f[y] && d[x]+it->se<d[y]){
d[y]=d[x]+it->se;p[y]=x;
q.push(make_pair(-d[y],y));
}
}
}
x=t;ans[y=1]=t;
while (p[x]){
ans[++y]=p[x];x=p[x];
}
printf("%d %d
",d[t],y);
for (i=y;i>0;i--)
printf("%d %d
",v[ans[i]].fi,v[ans[i]].se);
return 0;
}
晚安..睡觉了..
明天中午希望可以写点D7的题解吧..
希望明天加油...BLESS ALL
世界晚安...