Week5图 + acm第一次双周赛补题[蓝桥杯 2013 国 C] 危险系数思路：图的遍历思路：封锁阳光大学思路：Lily思路：思路：思路：

1
2
3
4
5
6
7
8
9
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6

1
2
2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<vector>

using namespace std;
vector <int> a[1000];	//数组a的每一个元素都是一个vector容器
int vis[1000]={0};		//用于标记某点是否已经走过
int cnt[1000]={0};		//记录走过某个点的次数
int ed,total=0;			//ed为终点，total表示走法数
int n,m;
void dfs(int now)		//深度优先搜索
{
	if(now==ed)			//确定搜索出口
	{
		total++;
		for(int i=1;i<=n;i++)
		{
			if(vis[i])cnt[i]++;	//若在这一次走法中i点走过则cnt【i】++
		}
		return;
	}
	for(int i=0;i<a[now].size();i++)
	{
		int next=a[now][i];	//走到下一个点
		if(vis[next]==0)	//判断下一个点是否走过
		{
			vis[next]=1;
			dfs(next);		//递归思想
			vis[next]=0;	//这一步很重要一定不能漏了！
		}
	}
}

int main()
{		
	cin>>n>>m;
	
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x].push_back(y);		//注意这是无向图
		a[y].push_back(x);
	}
	
	int st;
	cin>>st>>ed;		//起点st，终点ed
	vis[st]=1;			//先标记起点已走过
	dfs(st);
	
	int ans=0;			//ans记录关键点的个数
	for(int i=1;i<=n;i++)
	{
		if(cnt[i]==total)ans++;
	}
	ans-=2;			//排除起点和终点这两个点
	cout<<ans;
	
	return 0;
}

1
2
3
4
5
4 3
1 2
2 4
4 3

1
2
4 4 3 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<vector>

using namespace std;
const int N=100001;//本人在这里掉过坑，建议不要打擦边球，数组尽量开大一点
vector <int> a[N];	//储存有向图的点和边
int n,m;
int ma[N]={0};		//ma[j]表示某一点j能走到的最大的点
int vis[N]={0};
void dfs(int now)	//简单的深度搜索
{
	for(int i=0;i<a[now].size();i++)
	{
		int to=a[now][i];
		if(vis[to]==0)
		{
			vis[to]=1;
			ma[to]=ma[now];
			dfs(to);
		}
	}
}
int main()
{		
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		a[v].push_back(u);		//逆向思维，反向储存边
	}
	
	for(int i=n;i>=1;i--)		//注意是从数字大的点开始遍历
	{
		if(vis[i]==0)			//判断点i是否已经走过
		{
			ma[i]=i;			//先初始化
			dfs(i);
			vis[i]=1;			//标记点i已经走过了
		}	
	}
	
	for(int i=1;i<n;i++)cout<<ma[i]<<' ';
	cout<<ma[n];
	return 0;
}

1
2
3
4
5
3 3
1 2
1 3
2 3

1
2
Impossible

1
2
3
4
3 2
1 2
2 3

1
2
1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
struct Edge
{
    int t;
    int nexty;
}edge[200000];
int head[20000];
int cnt=0;//链式前向星
void add(int a,int b)//存边
{
    cnt++;
    edge[cnt].t=b;
    edge[cnt].nexty=head[a];
    head[a]=cnt;
}
bool used[20000]={0};//是否遍历过
int col[20000]={0};//每一个点的染色
int sum[2];//黑白两种染色各自的点数
bool dfs(int node,int color)//染色（返回false即impossible）
{
    if(used[node])//如果已被染过色
    {
        if(col[node]==color)return true;//如果仍是原来的颜色，即可行
        return false;//非原来的颜色，即产生了冲突，不可行
    }
    used[node]=true;//记录
    sum[col[node]=color]++;//这一种颜色的个数加1，且此点的颜色也记录下来
    bool tf=true;//是否可行
    for(int i=head[node];i!=0&&tf;i=edge[i].nexty)//遍历边
    {
        tf=tf&&dfs(edge[i].t,1-color);//是否可以继续染色
    }
    return tf;//返回是否完成染色
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int a,b;
    while(m--)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);//存的是有向边，所以存两次
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(used[i])continue;//如果此点已被包含为一个已经被遍历过的子图，则不需重复遍历
        sum[0]=sum[1]=0;//初始化
        if(!dfs(i,0))//如果不能染色
        {
            printf("Impossible");
            return 0;//直接跳出
        }
        ans+=min(sum[0],sum[1]);//加上小的一个
    }
    printf("%d",ans);//输出答案
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int main()
{
	int n;
	string r;
	cin>>n>>r;
	
	for(int i=0;i<n;i++)
	{
		if(r[i]=='.'&&(i==0&&r[i+1]!='L'||i==n-1&&r[i-1]!='L'||r[i-1]!='L'&&r[i+1]!='L'))
		r[i]='C';
	}
	
	if(n==1&&r[0]=='.')cout<<'C';	
	else cout<<r;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>

using namespace std;
int main()
{   
    static int num[1001],num2[1001],num3[2333];
    char n[1001];
    char n2[1001];
    cin>>n>>n2;
    int l2=strlen(n2),l=strlen(n);
    if(l<l2)
    {
        swap(l,l2);
        swap(n,n2);
    } 
    for(int i=l;i>=1;i--)
    {
        if(n[i-1]>='0'&&n[i-1]<='9')
        {
            num[l-i+1]=n[i-1]-'0';
        }
        else
        {
            num[l-i+1]=n[i-1]-'A'+10;
        }
    }
    for(int i=1;i<=l;i++)
    {
        if(num[i]>15)
        {
            num[i+1]++;
            num[i]%=16;
            continue;
        }
        break;
    }
    for(int i=l2;i>=1;i--)
    {
        if(n2[i-1]>='0'&&n2[i-1]<='9')
        {
            num2[l2-i+1]=n2[i-1]-'0';
        }
        else
        {
            num2[l2-i+1]=n2[i-1]-'A'+10;
        }
    }
    for(int i=1;i<=l2;i++)
    {
        if(num2[i]>15)
        {
            num2[i+1]++;
            num2[i]%=16;
            continue;
        }
        break;
    }
    int flag=0;
    for(int i=1;i<=l2;i++)
    {
        for(int j=1;j<=l;j++)
        {
            flag=(num[j]*num2[i]+num3[j+i-1])/16;
            num3[j+i-1]=(num[j]*num2[i]+num3[j+i-1])%16;
            num3[j+i]+=flag;
        }
    }
    int flag2=2333;
    while(num3[flag2]==0)
    {flag2--;}
    for(int i=flag2;i>0;i--)
    {
        if(!(i==flag2&&num3[i]==0))
        {
            if(num3[i]>9)
            {
                cout<<(char)(num3[i]-10+'A');
            }
            else
            {
                cout<<num3[i];
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>

using namespace std;
int n,d;
bool ccc(int a,int b)
{
    return a>b;
}
int check(long long s[],long long  x)
{
    long long t=s[0]-d;
    if(t<0)
    {t=0;}
    t+=x;
    for(int i=1;i<n;i++)
    {
        if(s[i]-t>d)
        {t+=s[i]-t-d;}
        else if(s[i]-t<0)
        {return 0;}
        t+=x;
    }
    return 1;
}
int main()
{
    cin>>n>>d;
    long long s[n];
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }   
    sort(s,s+n);
    long long l=1,r=1e8,mid,ans=0;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(s,mid))
        {
            l=mid+1;
            ans=max(mid,ans);
        }
        else
        {
            r=mid-1;
        }
    }
    cout<<ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+2;
int s,n,k;

struct tt
{
    int last,next=-2,id;
}t[maxn];
void exchange(int a)
{
    int c=a,d=0,i=a,k2;
    for(int j=1;j<=k;j++)
    {
        k2=t[i].last;
        swap(t[i].last,t[i].next);
        if(j==k)
        {d=i;}
         i=k2;
    }
    swap(t[c].last,t[d].next);
    if(t[d].next!=-1)
    {
        t[t[d].next].last=d;
    }
}
int main()
{   
    cin>>s>>n>>k;
    for(int i=0;i<n;i++)
    {
        tt ttt;
        int a;
        cin>>a>>ttt.id>>ttt.next;
        t[a].next=ttt.next;
        t[a].id=ttt.id;
    }
    t[s].last=-2;

    int js=0;
    for(int i=s;i>=0;i=t[i].next)
    {
        js++;
        if(t[i].next==-1)
        {break;}
    }
    n=js;
    js=0;
    int js2;
    for(int i=s;i>=0;i=t[i].next)
    {
        js++;
        if(js==n-n%k)
        {
            js2=i;
        }
        if(t[i].next==-1)
        {break;}
        t[t[i].next].last=i;
    }
    for(int q=1;q<=n/k;q++)
    {
        exchange(js2);
        if(t[js2].last!=-2)
        {
            t[t[js2].last].next=js2;
        }
        if(q==n/k)
        {
        }
        else
        {
            js2=t[js2].last;
        }
    }
    for(int i=js2;i>=0;i=t[i].next)
    {
        printf("%.5d %d ",i,t[i].id);
        if(t[i].next<0)
        {
            cout<<t[i].next<<endl;
        }
        else
        {
            printf("%.5dn",t[i].next);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
double a,b,c,d,p,q;
double f(double x)
{
    return a*pow(x,3)+b*pow(x,2)+c*x+d;
}

int main()
{
    int n;
    double eps=1e-7;
    cin>>n;
    for(int k=0;k<n;k++)
    {
        int flag=1;
        cin>>a>>b>>c>>d>>p>>q;
        double x1=(-2*b-sqrt(4*b*b-12*a*c))/(6*a);
        double x2=(-2*b+sqrt(4*b*b-12*a*c))/(6*a);
        if(x1>x2)
        {swap(x1,x2);}
        if(f(x1)<0)
        {flag=-1;}
        double l,r,mid;
        for(int aa=1;aa<=3;aa++)
        {
            if(aa==1)
            {l=p,r=x1;}
            else if(aa==2)
            {l=x1,r=x2,flag=-flag;}
            else if(aa==3)
            {l=x2,r=q,flag=-flag;}
            while(r-l>=eps)
            {
                mid=(l+r)/2;
                if(f(mid)*flag<0)
                {
                    l=mid+eps;
                }
                else
                {
                    r=mid-eps;
                }
            }
            printf("%.6lf ",mid);
        }
        printf("n");
    }
}