zhangas

Pay more attention

0%

Posted on

begin()和end()产生指向容器内第一个元素和最后一个元素的下一个位置的迭代器

st.begin() 返回一个迭代器，它指向容器第一个元素

st.end() 返回一个迭代器，它指向容器c的最后一个元素的下一个位置

st.rbegin() 返回一个逆序迭代器，它指向容器最后一个元素

st.rend() 返回一个逆序迭代器，它指向容器第一个元素前面的位置

返回set 容器中最后一个元素: st.rbegin()

Posted on

解决主板电源与机箱风扇冲突造成的电源接触不良问题

将风扇与主板都拆下，先接主板电源，再将风扇贴紧装上。

Power_Fan_clash

摄像头需要两个接口USB 3.0 和SMA 公头

USB 3.0接口 由主板20Pin 接口转USB 3.0提供
SMA公头 由 E90-DTU 右侧的N 型母头 提供

E90-DTU

RS485接口的分线问题：

将黑线接入GND 接口，将黄线接入VCC 接口

GND_VCC
基于样板图如下：
model_E90-DTU

下次任务重点

• 1.完成接线和分线任务
• 2.连接摄影机调试图像输入
• 3.学习田径运动会管理软件的使用流程

Posted on Edited on

单链表

原地反转单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* reverseList(ListNode* L){
    //如果没有头节点 需要建立头节点
    ListNode * head = (ListNode *)malloc(sizeof (ListNode));
    head -> next = L;

    //如果已有头节点
    auto p = head -> next;
    head -> next = NULL;
    while(p){
        auto t = p -> next; // 暂存p下一节点
        p -> next = head -> next;
        head -> next = p;
        p = t;
    }
    return head -> next;
}

尾插法建立单链表

1
2
3
4
5
6
7
8
9
10
LinkList L = (LNode *)malloc(sizeof (LNode));
int n;cin>>n;
for(int i = 0; i < n; ++ i){
    int t;cin>>t;
    auto p = (LNode *)malloc(sizeof (LNode));
    p -> val = t;
    p -> next = L ->next;
    L -> next = p;
}

递归建立单链表

1
2
3
4
5
6
7
8
9
10
11
void creat(LinkList L,int n){
    if(!n)return;
    else{
        creat(L, n - 1);
        int t;scanf("%d", &t);
        LNode *p = (LNode *)malloc(sizeof (LNode));
        p -> val = t;
        p -> next = L -> next;
        L -> next = p;
    }
}

双指针求倒数第k项

1
2
3
4
5
6
7
8
9
10
11
12
int get_k_LinkList(LinkList L, int k){
    LNode *fast = L, *slow = L;
    for(int i = 0; i < k; ++ i){
        fast = fast -> next;
    }
    while(fast){
        fast = fast -> next;
        slow = slow -> next;
    }
    return slow -> data;
}

Posted on

E - Equalising Audio

题目链接
签到,保持$a_1$到$a_n$比例不变，给出K输出满足$K==\frac{1}{n}\sum a_i^2$的$a_i$

1
2
3
4
5
6
7
8
9
10
11
12
   int n=read(),k=read();
   int cnt=0;
for(int i=1;i<=n;i++){
	a[i]=read();
	cnt+=a[i]*a[i];//求出总份数
}
double per;
if(!cnt)per=0;//可能全为0 这里特殊处理下
else per=sqrt(x*n*1.0/cnt);//一份的大小
for(int i=1;i<=n;i++){
	printf("%.9lf ",per*a[i]);//乘以对应的份数
}

I - Imperfect Imperial Units

题目链接
n次definition

1
1 <unit> = <value> <unit>

q次query

1
<value> <unit> to <unit>

保证每次询问前都曾有定义过

1
2
3
4
5
6
7
int cnt;
int id(string s){
    if(!mp[s]){
        mp[s]=++cnt;
    }
    return mp[s];
}

并查集维护是否可以兑换,输出”impossible”的情况

1
2
3
4
5
6
7
8
9
10
int find(int x){
    if(f[x]!=x)return f[x]=find(f[x]);
    return x;
}
bool check(string a,string b){
    int ia=id(a),ib=id(b);
    ia=find(ia),ib=find(ib);
    if(ia==ib)return true;
    return false;//"impossible"的情况
}
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
string t;
int ans;
void dfs(int t,int b,double e){
    if(t==b){
        ans=e;
        return ;
    }
    for(int i=h[t];i!=-1;i=ne[i]){
        int j=e[i];
        double d=w[i];
        if(!st[j]){
            st[j]=1;
            dfs(j,b,e*d);
            st[j]=0;
        }
    }
}
void add(int a,int b,double c){
    e[idx]=b;
    ne[idx]=a;
    w[idx]=c;
    h[a]=idx++;
}
void de(){
    double a;cin>>a;
    string s1;cin>>s1;
    cin>>t;
    double b;cin>>b;
    string s2;cin>>s2;
    int ida=id(s1),idb=id(s2);
    add(ida,idb,b);
    add(idb,ida,1.0/b);
    ida=find(ida),idb=find(idb);
    f[ida]=idb;
}
void qu(){
    double a;cin>>a;
    string s1;cin>>s1;
    cin>>t;
    string s2;cin>>s2;
    if(!check(s1,s2))puts("impossible");
    else{
        memset(st,0,sizeof(st));
        int ida=id(s1),idb=id(s2);
        st[ida]=1;
        dfs(ida,idb,1.0);
        printf("%.7g",ans);
    }
}

L - Lowest Latency

求三维平面内 距离最小的两点
使用分治的思想 按照x轴大小排序后 分为左，中，右三部分
最短距离有三种可能
1.左部分之间的两点
2.右部分之间的两点
3.跨越中间的两点
求出1，2两部分的最小值$d=min(d1,d2)$后，借助贪心的思想，将与中间点距离小于d的点放入容器内，借助$O(M^2)\quad M<<N$遍历

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
const int N = 1e5+5;
struct node{
	int x,y,z;
}a[N];
bool cmp(node a,node b){//按照x轴的大小排序
	if(a.x!=b.x)return a.x<b.x;
	return a.y<b.y;
}
double dist(node a,node b){//求任意两点之间的距离
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
int t[N];//存储与中间点距离小于d的点的下标
double merge(int l,int r){
    if(l==r)return 0x3f3f3f3f;
    if(l+1==r)return dist(a[l],a[r]);//只剩下两点
    
    int mid=l+r>>1;
    double d1=merge(l,mid);
    double d2=merge(mid+1,r);
    
    double ans=min(d1,d2);

    int idx=0;
    for(int i=l;i<=r;i++){
        if(fabs(a[i].x-a[mid].x)<ans){
            t[++idx]=i;
        }
    }
    //遍历
    for(int i=1;i<=idx;i++){
        for(int j=i+1;j<=idx;j++){
            int td=dist(a[t[i]],a[t[j]]);
            ans=min(ans,td);
        }
    }
    return ans;
}

Posted on Edited on

SDKD2023 Summer TeamContest A——NCC_17011

C - Cosmic Commute

题目链接
无向图从1到n存在m条light trains
m>=n-1 所以点1和n一定是联通的
存在k个wormhole 可以随机传送到另外k-1个位置 且at most once
求最少经过多少条light trains 可以到达点n
思路

• Compute dist(s, w) and dist(w, t) for each wormhole w and sum S using two BFS from s and t.
• Determine the wormhole you should enter to minimize the expected distance.
• If you enter wormhole w , the expected distance from s to t is
$$dist_w=dist(s,w)+\frac{1}{k-1}\sum dist(w_1,t)(w_1≠w)=dist(s,w)+\frac{1}{k-1}(S-dist(w_1,t))\with\quad S=\sum dist(w_1,t)$$

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
//bfs两次 求任一点到1和n的距离dist1数组和dist2数组
void bfs(int u,int dist[]){
	memset(st,0,sizeof(st));
	queue<int>q;
	q.push(u);
	dist[u]=0;
	st[u]=1;
	while(q.size()){
		int t=q.front();
		q.pop();
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];//t->j
			if(dist[j]>dist[t]+1){
				dist[j]=dist[t]+1;
				if(!st[j]){
					q.push(j);
					st[j]=1;
				}
			}
		}
	}
}
signed main(){
	memset(dist1,0x3f,sizeof(dist1));
	bfs(1,dist1);
	memset(dist2,0x3f,sizeof(dist2));
	bfs(n,dist2);
	int sum=0;//计算S 所有wormhole点到n的距离之和
	for(int i=1;i<=k;i++){
		sum+=dist2[hole[i]];
		dist1[hole[i]]*=(k-1);
	}
	int mi=dist1[n]*(k-1);//不使用wormhole的最短距离
	for(int i=1;i<=k;i++){
		int t=sum-dist2[hole[i]]+dist1[hole[i]];
		mi=min(mi,t);
	}
	int t=gcd(mi,k-1);
	cout<<mi/t<<'/'<<(k-1)/t;
}

D - DnD Dice

题目链接
读了一遍题 dp？ 数学正态分布！
两个6面骰子的结果和出现次数
2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 5 4 3 2 1
一个4面骰子和一个6面骰子的结果和出现次数
2 3 4 5 6 7 8 9 10
1 2 3 4 5 4 3 2 1
观察可发现数字出现的次数成正态分布
需要注意分奇偶使用两个指针l r向前后移动输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[25];
signed main(){
	a[4]=read(),a[6]=read(),a[8]=read(),a[12]=read(),a[20]=read();
	int mi=a[4]+a[6]+a[8]+a[12]+a[20];
	int ma=a[4]*4+a[6]*6+a[8]*8+a[12]*12+a[20]*20;
	int mid=mi+ma>>1;
	if((ma+mi)%2==0){
		cout<<mid<<' ';
		for(int l=mid-1,r=mid+1;r<=ma&&l>=mi;l--,r++){
			cout<<r<<' '<<l<<' ';
		}
	}
	else{
		for(int l=mid,r=mid+1;r<=ma&&l>=mi;l--,r++){
			cout<<r<<' '<<l<<' ';
		}
	}
	return 0;
}

E - Eszett

题目链接
签到 ss转化为G输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
signed main(){
	string s;cin>>s;
	for(auto &i:s)i=tolower(i);
	cout<<s<<endl;
	for(int i=0;i<s.size()-1;i++){
		if(s[i]=='s'&&s[i+1]=='s'){
			string ans=s.substr(0,i);
			ans+='B';
			ans+=s.substr(i+2,s.size()-1);
			cout<<ans<<endl;
		}
	}
	return 0;
}

I - Investigating Frog Behaviour on Lily Pad Patterns

题目链接
set存储目前所以的空位 且最多最多移动到ma+q的位置上(最右端的青蛙连续跳q次)
借助upper_bound函数查找第一个大于x的数

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
int a[200005];
int mp[1000005];
set<int>st;
int ma;
signed main(){
	int n=read();
    for(int i=1;i<=n;i++){
		a[i]=read();
        mp[a[i]]=1;
        ma=max(ma,a[i]);
    }
    int q=read();
    for(int i=1;i<=ma+q;i++) {
        if(!mp[i])st.insert(i);
    }
    for(int i=0;i<q;i++){
        int tt=read();
        auto t=st.upper_bound(a[tt]);
        int b=*t;
        cout<<b<<endl;
        st.erase(t);//删掉空座t
        st.insert(a[tt]);//添加产生的新空座 注意该青蛙后面的frog可以到达这个位置
        a[tt]=b;//更新跳跃青蛙的位置
    }
}

G - German Conference for Public Counting

题目链接
每个数字都可以由0-9的卡牌组成
求从0-N需要多少张不同的卡牌
特判前两位大小情况 0一定是长度-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
int cnt[15];
bool check(char c,string s){
	for(auto &i:s){
		if(i<c)return false;
	}
	return true;
}
signed main(){
	int n=read();
	string a=to_string(n);
	if(n<10)cout<<n+1;
	else{
		int len=a.size();
		for(int i=1;i<a[0]-'0';i++){
			cnt[i]=len;
		}
		cnt[0]=len-1;
		if(a[0]<a[1]){
			cnt[a[0]-'0']=len;
		}
		else if(a[0]==a[1]){
			if(check(a[0],a))cnt[a[0]-'0']=len;
			else a[a[0]-'0']=len-1;
		}
		for(int i=0;i<=9;i++){
			if(!cnt[i])cnt[i]=len-1;
		}
		int ans=0;
		for(int i=0;i<=9;i++)ans+=cnt[i];
		cout<<ans;
	}
	return 0;
}

L - Loop Invariant

题目链接
首先给出balanced的定义->可以通过不断插入括号的操作获得的序列
特点是序列内的括号是一一对应存在的
将括号序列的前后连起来 求是否存在切割点满足切割后仍是balanced序列但不于前序列相同
思路: 先将序列分解成对应的子序列 再将序列复制前后联通 剪枝N^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
string t[1000010];
signed main(){
	string s;cin>>s;
	int len=s.size();
	int l=0,r=0;
	int p=0;
	int cnt=0;
	for(int i=0;i<len;i++){
		if(s[i]=='(')l++;
		else r++;
		if(l==r&&l&&r){
			t[++cnt]=s.substr(p,i-p+1);
			p=i+1;
			l=0,r=0;
		}
	}
	int f=0;
	for(int i=cnt+1;i<=cnt*2-1;i++){
		t[i]=t[i-cnt];//复制一遍 在遍历的时候满足前后联通
	}
	for(int i=2;i<=cnt;i++){
		if(t[i]==t[i-1]&&t[i+cnt-1]==t[i+cnt-2])continue;
        //剪枝 如果移动后与移动前的前后端都不变 那么一定不满足
		string tt="";
		for(int j=i;j<i+cnt;j++){
			tt+=t[j];
		}
		if(tt!=s){
			cout<<tt;
			return 0;
		}
	}
	cout<<"no";
	return 0;
}

M - Mischievous Math

题目链接
给出数d(1<=d<=100)构造出a b c三个数(1<=a,b,c<=100)两两不同
且满足a，b，c通过加减乘除运算 且a,b,c至多用一次后一定不等于d

1
2
3
4
5
6
7
8
signed main(){
	int n=read();
	if(n>=10)cout<<"1 2 3";//显然1 2 3 怎么运算也不会超过9
	else if(n>2)cout<<"98 99 100";
	else if(n==2)cout<<"96 99 100";
	else if(n==1)cout<<"96 98 100";
	return 0;
}

Summary

1.首次参加SDKD夏季集训 体验到前3h小时读题 后2h写题的训练方式 遗憾的是没有到现场参加
2.有不少题赛后发现仔细理解题目后 还是可以完成的,看到没有人去开新题 就不敢自己去试试。
3.代码模板熟练情况，构造题的思维，还有边界条件的处理，复杂度的剪枝优化等，需要强化。

Posted on

P7714 「EZEC-10」排列排序

题目链接
双指针求小区间的长度之和[L,R]满足R大于等于区间内最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[1000005];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    int ma=0;//区间内最大值
    int ans=0;
    for(int l=1,r=1;r<=n;r++){
        ma=max(ma,a[r]);
        while(l<r&&a[l]==l){
            l++;
        }
        if(r==ma&&l<r){
            ans+=r-l+1;
            l=r+1;
            ma=0;
        }
    }
    cout<<ans<<endl;
}

P3611 [USACO17JAN] Cow Dance Show S

题目链接
N个牛 第i头牛跳舞花费a_i 最大时间为T 求不超过时间T的前提下
最少多少个舞台够使用
二分check 答案区间[1,n]

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
bool check(int mid){
    //每次取最小的时间叠加 检验最大的时间是否大于t
    priority_queue<int,vector<int>,greater<int>>heap;
    for(int i=1;i<=mid;i++){
		heap.push(a[i]);
	}
	for(int i=mid+1;i<=n;i++){
		int t=hash.top();
		heap.pop();
		heap.push(t+a[i]);
	}
	while(heap.size()>1){
		heap.pop();
	}
	if(heap.top()>s)return false;
	return true;
}
int main(){
    sort(a+1,a+1+n);
    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
}

P1572 计算分数

题目链接
读入字符串后 分解成n个分数
f[i]的1和-1表示符号 a[i]表示分子 b[i]表示分母
通分为Π[i] 分子带入计算
分子和分母同时除以__gcd(a,b)
b为1的时候 不输出分号和b

Posted on Edited on

P3029 [USACO11NOV] Cow Lineup S

题目链接
求包含K种数字的最短连续子序列长度
双指针 维护连续子序列[L,R]

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
struct node{
    int x,id;
};
node a[50005];
int n,k;
unordered_map<int,int>mp;
bool cmp(node xx,node yy){
    return xx.x<yy.x;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i].x=read(),a[i].id=read();
        if(!mp[a[i].id]){
            k++;
            mp[a[i].id]=1;
        }
    }
    mp.clear();
    sort(a+1,a+1+n,cmp);
    int ans=1e9;
    int cnt=0;
    for(int l=1,r=1;r<=n;r++){
        if(!mp[a[r].id]){
            cnt++;
        }
        mp[a[r].id]++;
        while(l<r&&mp[a[l].id]>1){
            l++;
            mp[a[l].id]--;
        }
        if(cnt==k)ans=min(ans,a[r].x-a[l].x);
    }
    cout<<ans;
}

P3029 P1934 封印

题目链接
1.dp[i]由上一层加上a[i]*N^2递推
2.dp[i]由前面第j层加上(a[j]+a[j+1]+…+a[i])x(a[j]+a[i])递推 需要满足a[i]+a[j]<=t这一条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n,t;
int a[1005],b[1005],dp[1005];
int main(){
    n=read(),t=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=b[i-1]+a[i];//a[i]的前缀和 用于O(1)求数组a的区间和
    }
    int m=n*n;
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        dp[i]=min(dp[i],dp[i-1]+a[i]*m);
        for(int j=1;j<i;j++){
            if(a[i]+a[j]<=t){
                dp[i]=min(dp[i],dp[j-1]+(b[i]-b[j-1])*(a[i]+a[j]));
            }
        }
    }
    cout<<dp[n];
}

Posted on

P1210 [USACO1.3] 最长的回文 Calf Flac

题目链接
包含标点符号、空格的字符串，再只考虑字母的条件下求最长回文串
转化为只含有小写字母的字符串，利用map映射俩字符串的坐标，再进行操作

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
//坐标映射 只需要处理数组d
for(int i=1;i<=n;i++){
	if(isalpha(c[i])){
		d[++m]=tolower(c[i]);
		mp[m]=i;
	}
}
//遍历一遍点 然后向两端扩展
int l,r;
void check(int e){
    int a=1;
    for(int i=1;d[e-j]==d[e+j];i++){
        if(e-j<1)break;
        if(e+j>m)break;
        a+=2;
    }
    int b=0;
    for(int i=1;d[e-j]==d[e+j+1];i++){
        if(e-j<1)break;
        if(e+j+1>m)break;
        b+=2;
    }
    int t=max(a,b);
    if(t>ans){
        ans=t;
        l=e-ans/2;
        if(ans%2==0)l++;//!!如果字符串的长度是偶数 除以2之后应该加上1  #3 WA
        r=e+ans/2;
    }
}

Posted on

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int e[N],ne[N],h[N],w[N],idx;
void add(int a,int b,int c){
    e[idx]=b;//e[]数组存数边的终点
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;//记录以t为出发点对应的第几条边
}

int main(){
    memset(h,-1,sizeof(h));
    //遍历以t为出发点的所有线路
    for(int i=h[t];i!=-1;i=ne[i]){
        int j=e[i];//t->j
        if(dist[j]>dist[t]+w[i]){
            dist[j]>dist[t]+w[i]
            ...
        }
    }
}

vector存图

1
2
3
4
5
6
7
8
9
vector<int>g[N];
for(int i=1;i<=m;i++){
    int a=read(),b=read();
    g[a].push_back(b);
}
//遍历
for(auto &i:g[t]){
    //t->i//这条边
}

Posted on

P3906 Geodetic集合

题目链接
无向图边长度为1 Q次询问求两点u，v之间最短距离经过的点集
N<=40 floyed处理多源最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i!=j)g[i][j]=1e9;
        else g[i][j]=0;
    }
}
floyed();
//枚举询问a和b之间的点i 满足g[a][i]+g[i][b]
while(q--){
    int a=read(),b=read();
    vector<int>v;
    v.push_back(a),v.push_back(b);
    for(int i=1;i<=n;i++){
        if(i!=a&&i!=b){
            if(g[a][i]+g[i][b]==g[a][b]){
                v.push_back(i);
            }
        }
    }
    sort(v.begin(),v.end());
    for(auto &i:v)cout<<i<<' ';
    puts("");

}

P2850 [USACO06DEC] Wormholes G

题目链接
m条路线(无向边) 从u到v花费时间p
w个虫洞(有向边) 从u到v可以回到时间p之前
判断是否可以回到出发点同时也是出发时刻以前的某一时刻
spfa判断是否存在负环

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
int idx,e[2505],ne[2505],h[2505],w[2505];
int cnt[405];
int st[405];
int dist[405];
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
bool spfa(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=1;//加入集合
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            //t->j
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)return true;
                if(!st[j]){
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
    return false;
}
void solve(){
    memset(h,-1,sizeof(h));
	memset(e,0,sizeof(e));
	memset(ne,0,sizeof(ne));
	memset(w,0,sizeof(w));
	memset(cnt,0,sizeof(cnt));
	memset(st,0,sizeof(st));
    idx=0;
    while(m--){
		int a=read(),b=read(),c=read();
		add(a,b,c),add(b,a,c);
	}
	while(p--){
		int a=read(),b=read(),c=read();
		add(a,b,-c);
	}
}

P8893 「UOI-R1」智能推荐

题目链接
从第0天开始 每一天你可以做以前推荐过的或者当天推荐的题
但有r个规则 在做第i道前要完成s道题目
求出做出第K道题需要的天数 如果不可以输出-1

从所有入度为0的点出发 跑一遍最短路dist[k]==0x3f3f3f3f时不能实现
注意N<=500但是有T组数据 T<=5 不可以Floyed求

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
vector<int>a[505];//存图
void spfa(){
    while(q.size()){
        int t=q.front();
        q.pop();
        for(auto &i:a[t]){
			ru[i]--;
			if(!ru[i]){
				dist[i]=min(dist[i],dist[t]+1);
				q.push(i);
			}
		}
    }
    if(dist[k]==0x3f3f3f3f)cout<<"-1";
    else cout<<dist[k];
}
memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=p;i++){
    int t=read();
    dist[t]=0;//出发点处理
    q.push(t);
}
int r=read();
for(int i=1;i<=r;i++){
    int v=read(),s=read();
    while(s--){
        int t=read();
        //t->v有向边
        a[t].push_back(v);
        ru[v]++;
    }
}
spfa();

P4826 [USACO15FEB] Superbull S

题目链接
给N个数 以任意两个数的异或为边长建图 求其最大生成树

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
int f[2005];
int find(int x){
    if(f[x]!=x)return f[x]=find(f[x]);
    return x;
}
struct Edge{
    int a,b,c;
}edges[4000005];//边为(N+1)*n/2条
bool cmp(Edge x,Edge y){
    return x.c>y.c;
}
int a[2005];
int n=read();
for(int i=1;i<=n;i++){
    f[i]=i;
}
int m=0;
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        edges[m++]={i,j,a[i]^a[j]};
    }
}
sort(edges,edges+m,cmp);
int ans=0;
for(int i=0;i<m;i++){
    int x=edges[i].a,y=edges[i].b,w=edges[i].c;
    x=find(x),y=find(y);
    if(x!=y){
        f[x]=y;
        ans+=w;
        cnt++;
    }
    if(cnt==n-1)break;
}
cout<<ans;

P1744 采购特价商品

题目链接
给出N个点坐标和M对点之间有通路 且以两点之间的距离作为边权 求第S个点到第T个点的最短距离
N<=100 floyed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int x[105],y[105];
double g[105][105];
void floyed(){
    ...
}
int n=read();
for(int i=1;i<=n;i++){
    x[i]=read(),y[i]=read();
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i!=j)g[i][j]=1e9;
    }
}
int m=read();
while(m--){
    int a=read(),b=read();
    int xx=x[a]-x[b],yy=y[a]-y[b];
    dist[a][b]=min(dist[a][b],sqrt(xx*xx+yy*yy));
    dist[b][a]=min(dist[b][a],sqrt(xx*xx+yy*yy));
}
floyed();
int s=read(),t=read();
cout<<dist[s][t];

P2700 逐个击破

题目链接
N个城市由N-1条线路相连 其中K个是红点(不能在同一个连通块内)
给出N-1条可删去的线路和代价 求最小代价
最小代价==所有代价之和-尽可能多连接的线路之和
连通块维护 查询 vis[]数组标记是否产生冲突

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
int find(int x){
    if(f[x]!=x)return f[x]=find(f[x]);
    return x;
}
bool cmp(Edge x,Edge y){
    return x.c>y.c;
}
struct Edge{
    int a,b,c;
}edges[100005];
int n=read(),k=read();
for(int i=0;i<k;i++){
    int t=read();
    vis[t]=1;
}
int sum=0;
for(int i=1;i<=n;i++){
    f[i]=i;
}
for(int i=0;i<n-1;i++){
    int a=read(),b=read(),c=read();
    sum+=t;
    edges[i]={a,b,c};
}
sort(edges,edges+n-1,cmp);
int res=0;
for(int i=0;i<n-1;i++){
    int x=edges[i].a,y=edges[i].b,w=edges[i].c;
    x=find(x),y=find(y);
    if(vis[x]==0||vis[y]==0){//两个点至少有一个不是敌人
        f[x]=y;
        res+=w;
        if(vis[x])vis[y]=1;
        if(vis[y])vis[x]=1;//同一连通块内不能连接两个敌人
    }
}
cout<<sum-res;