训练

1.抢红包（结构体排序，但是有输出要求，被ban得死死的）

cmp函数也可替换为（不过可能有时候会用错，但不失为一种简便方法）

bool cmp(int x,int y)
{
    if(ren[x]==ren[y])return bao[x]>bao[y];
    return ren[x]>ren[y];
}
。。。
sort(id+1,id+1+n,cmp);

代码：

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 struct human{
 5     int mo;
 6     int id;
 7     int bao;
 8 };
 9 struct human h[10000];
10 bool cmp(human x,human y)
11 {
12     if(x.mo==y.mo)
13     {
14         if(x.bao==y.bao)
15         {
16             return x.id<y.id;
17         }
18         return x.bao>y.bao;
19     }
20     return x.mo>y.mo;
21 }
22 signed main()
23 {
24     int n;
25     cin>>n;
26     for(int i=1;i<=n;i++)
27     {
28         h[i].id=i;
29         h[i].mo=0;
30         h[i].bao=0;
31     }
32     for(int i=1;i<=n;i++)
33     {
34         int fa;
35         cin>>fa;
36         int sum=0;
37         for(int j=0;j<fa;j++)
38         {
39             int ren,qian;
40             cin>>ren>>qian;
41             h[ren].mo+=qian;
42             h[ren].bao++;
43             sum+=qian;
44         }
45         h[i].mo-=sum;
46     }
47     sort(h+1,h+1+n,cmp);
48     for(int i=1;i<=n;i++) {
49         double x = h[i].mo;
50         x/=100;
51         cout << h[i].id << ' ' << fixed << setprecision(2) << x << endl;//引起重视，天梯要看清要求还是
52     }
53     return 0;
54 }

2.列车厢调度（stl栈的运用，每次先判断1的顶端，不符再判断3，如果3此时也不符，将1的top元素转移至3，最后如果3中还有元素再判断，否则输出kiding）

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 stack<char> m,p,k;
 5 stack<char> n;
 6 string w[50];
 7 signed main()
 8 {
 9     string s,c;
10     cin>>s>>c;
11     int h=s.size();
12     for(int i=0;i<h;i++){
13         k.push(s[i]);
14     }
15     while(!k.empty()){
16         n.push(k.top());
17         k.pop();
18     }
19     int ans=0,res=0;
20     int b=0;
21     while(!n.empty()) {
22         if (n.top() == c[res]) {
23             w[ans++] = "1->2";
24             n.pop();
25             b++;
26             res++;
27         } else {
28             if (!p.empty()&&p.top() == c[res] ) //如果这里的判断顺序反了则会段错误，抽象
　　　　　　　　　{
29                 w[ans++] = "3->2";
30                 p.pop();
31                 b++;
32                 res++;
33             } else {
34                 w[ans++] = "1->3";
35                 p.push(n.top());
36                 n.pop();
37                 b++;
38             }
39         }
40     }
41     while (!p.empty()) {
42         if (p.top() == c[res]) {
43             w[ans++] = "3->2";
44             p.pop();
45             b++;
46             res++;
47         }
48         else
49         {
50             cout<<"Are you kidding me?"<<endl;
51             return 0;
52         }
53     }
54     for(int i=0;i<ans;i++)
55     {
56         cout<<w[i]<<endl;
57     }
58     return 0;
59 }

3.连续因子（循环更新连续数字串长度，考虑最小这个因素的时侯发现至多存在一个最长字串，所以从小向大遍历即可）

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 signed main()
 5 {
 6     int n;
 7     cin>>n;
 8     int s=0,l=0; 
 9     for(int i=2;i<sqrt(n)+1;i++)
10     {
11         int tmp=1;
12         for(int j=i;tmp*j<=n;j++)//保证连续且都为n的因子
13         {
14             tmp*=j;
15             if(n%tmp==0&&j-i+1>l)//大于l就更新最大长度
16             {
17                 s=i;//开始数字
18                 l=j-i+1;//字串长度
19             }
20         }
21     }
22     if(s==0)cout<<1<<endl<<n<<endl;
23     else 
24     {
25         cout<<l<<endl;
26         for(int i=s;i<s+l;i++)
27         {
28             cout<<i;
29             if(i!=s+l-1)cout<<'*';
30         }
31         cout<<endl;
32     }
33     return 0;
34 }

4. 哈利·波特的考试（无向有权图最短路，用dijkstra）

代码

 1  1 #include<bits/stdc++.h>
 2  2 #define int long long
 3  3 using namespace std;
 4  4 #define maxInt 2147483647
 5  5 typedef struct
 6  6 {
 7  7     int arcs[102][102];
 8  8     int vexnum,arcnum;
 9  9 }AMGraph;
10 10 int S[102];  //记录源点v0到v1是否已经被确定最短路径长度
11 11 int D[102];  //记录v0到vi的当前最短路径长度
12 12 int Path[102]; //记录v0到vi的当前最短路径vi的前驱
13 13 int n,i,u,j,m,v,mi,w,a,b,c,min1 = 999999,ma = -991111,p = 0;
14 14 void Dijkstra(AMGraph G,int v0)
15 15 {
16 16     n = G.vexnum;
17 17     for(v = 0;v < n;v ++)
18 18     {
19 19         S[v] = 0;
20 20         D[v] = G.arcs[v0][v];
21 21         if(D[v] < maxInt)    Path[v] = v0;
22 22         else Path[v] = -1;
23 23     }
24 24     S[v0] = 1;
25 25     D[v0] = 0;
26 26     //初始化结束；
27 27     for(i = 1;i < n;i ++)
28 28     {
29 29         mi  = maxInt;
30 30         for(w = 0;w < n;w ++)
31 31             if(!S[w] && D[w] < mi)
32 32             {
33 33                 mi = D[w];
34 34                 v = w;
35 35             }
36 36         S[v] = 1;
37 37         for(w = 0;w < n;w ++)
38 38             if(!S[w] && (D[v] + G.arcs[v][w] < D[w]))
39 39             {
40 40                 D[w] = D[v] + G.arcs[v][w];
41 41                 Path[w] = v;
42 42             }
43 43     }
44 44 }
45 45 signed main()
46 46 {
47 47     AMGraph G;
48 48     memset(S,0,sizeof(S));
49 49     memset(D,0x3f3f3f3f,sizeof(D));
50 50     memset(G.arcs,0x3f3f3f3f,sizeof(G.arcs));   //邻接矩阵一定要初始化
51 51     scanf("%d %d",&G.vexnum,&m);
52 52     for(i = 0;i < m;i ++)
53 53     {
54 54         scanf("%d %d %d",&a,&b,&c);
55 55         G.arcs[a - 1][b - 1] = c;
56 56         G.arcs[b - 1][a - 1] = c;
57 57     }
58 58     for(u = 0;u < G.vexnum;u ++)
59 59     {
60 60         ma = -9999999;
61 61         Dijkstra(G,u);
62 62         for(j = 0;j < G.vexnum;j ++)
63 63         {
64 64             if(D[j] > ma)
65 65                 ma = D[j];
66 66         }
67 67         if(ma < min1)
68 68         {
69 69             min1 = ma;
70 70             p = u + 1;
71 71         }
72 72 
73 73     }
74 74     if(p == 0)
75 75         printf("0");
76 76     else
77 77         printf("%d %d\n",p,min1);
78 78     return 0;
79 79 }

堆优化模板

 1 typedef pair<int, int> PII;
 2 
 3 int n;      // 点的数量
 4 int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
 5 int dist[N];        // 存储所有点到1号点的距离
 6 bool st[N];     // 存储每个点的最短距离是否已确定
 7 
 8 // 求1号点到n号点的最短距离，如果不存在，则返回-1
 9 int dijkstra()
10 {
11     memset(dist, 0x3f, sizeof dist);
12     dist[1] = 0;
13     priority_queue<PII, vector<PII>, greater<PII>> heap;
14     heap.push({0, 1});      // first存储距离，second存储节点编号
15 
16     while (heap.size())
17     {
18         auto t = heap.top();
19         heap.pop();
20 
21         int ver = t.second, distance = t.first;
22 
23         if (st[ver]) continue;
24         st[ver] = true;
25 
26         for (int i = h[ver]; i != -1; i = ne[i])
27         {
28             int j = e[i];
29             if (dist[j] > distance + w[i])
30             {
31                 dist[j] = distance + w[i];
32                 heap.push({dist[j], j});
33             }
34         }
35     }
36 
37     if (dist[n] == 0x3f3f3f3f) return -1;
38     return dist[n];

floyd做法

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int mp[105][105];//定义图 
 4 int n,m;//节点和边 
 5 #define inf 88888888
 6 int dis[105];//记录距离其他点到这个点的最大距离 
 7 void floyd()
 8 {
 9     for(int k=1;k<=n;k++)
10     {
11         for(int i=1;i<=n;i++)
12         {
13             for(int j=1;j<=n;j++)
14             {
15                 if(mp[i][j]>mp[i][k]+mp[k][j]&&k!=i&&k!=j&&i!=j)
16                 mp[i][j]=mp[i][k]+mp[k][j];
17 
18             }
19         }
20     }
21 } 
22 
23 int main()
24 {
25     cin>>n>>m;
26     
27     for(int i=1;i<=n;i++)
28     {
29         for(int j=1;j<=n;j++)
30         {
31             mp[i][j]=inf;//初始值全赋值为最大 
32         }
33     }
34     
35     for(int i=1;i<=m;i++)
36     {
37         int x;
38         int y;
39         int d;
40         scanf("%d %d %d",&x,&y,&d);
41         mp[x][y]=d;
42         mp[y][x]=d;
43     }
44     
45     floyd(); 
46     memset(dis,0,sizeof(dis));
47     
48     for(int i=1;i<=n;i++)
49     {
50         for(int j=1;j<=n;j++)
51         {
52             if(dis[i]<mp[i][j]&&i!=j)dis[i]=mp[i][j];
53         }
54     }
55     
56     int mm = inf;
57     int from;
58     for(int i=1;i<=n;i++)
59     {
60         if(mm>dis[i])
61         {
62             mm=dis[i];
63             from = i;
64     }
65     if(mm==inf)cout<<"0";
66     else cout<<from<<" "<<mm; 
67     
68     return 0;
69 } 

5.排座位（树的应用,构造一个树，如果他们是朋友就统一父节点，不是就互相存进数组中，父节点是否相同和各自数组有无对方元素来判断输出）

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int fa[1000000];
 5 int find(int x)
 6 {
 7     if(fa[x]==x)return x;
 8     return fa[x]=find(fa[x]);
 9 }
10 void unity(int a,int b)
11 {
12     int Fa=find(a),Fb=find(b);
13     fa[Fa]=Fb;
14 }
15 signed main()
16 {
17     int n,m,k;
18     cin>>n>>m>>k;
19     vector<set<int>>v(n+1);
20     for(int i=1;i<=n;i++)
21         fa[i]=i;
22     for(int i=0;i<m;i++)
23     {
24         int a,b,c;
25         cin>>a>>b>>c;
26         if(c==1)unity(a,b);
27         else
28         {
29             v[a].insert(b);
30             v[b].insert(a);
31         }
32     }
33     while(k--)
34     {
35         int a,b;
36         cin>>a>>b;
37         int x=0,y=0;
38         if(find(a)==find(b))
39             x++;
40         if(v[a].count(b))
41             y++;
42         if(x&&y)cout<<"OK but..."<<endl;
43         else if(!x&&y)cout<<"No way"<<endl;
44         else if(x&&!y)cout<<"No problem"<<endl;
45         else cout<<"OK"<<endl;
46     }
47     return 0;
48 }