B.Guest Student
題目：
鏈接：https://ac.nowcoder.com/acm/contest/7854/B
來源：牛客網

Berland State University invites people from all over the world as guest students. You can come to the capital of Berland and study with the best teachers in the country.
Berland State University works every day of the week, but classes for guest students are held on the following schedule. You know the sequence of seven integers a1, a2, …, a7 (ai = 0 or ai = 1):
a1 = 1 if and only if there are classes for guest students on Sundays;
a2 = 1 if and only if there are classes for guest students on Mondays;
…
a7 = 1 if and only if there are classes for guest students on Saturdays.
The classes for guest students are held in at least one day of a week.
You want to visit the capital of Berland and spend the minimum number of days in it to study k days as a guest student in Berland State University. Write a program to find the length of the shortest continuous period of days to stay in the capital to study exactly k days as a guest student.

題意：
一個禮拜七天，給出每天可以得到的數字，要么是0要么是1.先給出N，是你想要得到的1的個數，問要得到N個1最少需要多少天。

思路：
這道題我分為14天以內和14天之外來考慮的。因為大于14天的話，大于的部分都需要完整的7天才能得到。那14天之內的話，是不需要完整的7天的，因為它可以從任意的一天開始。

代碼：

#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){int k = 0, f = 1; char c = getchar();for(;!isdigit(c); c = getchar())if(c == '-') f = -1;for(;isdigit(c); c = getchar())k = k * 10 + c - '0';return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010 int a[60]; int main() {int t;scanf("%d",&t);while(t--){int k;scanf("%d",&k);int num = 0;int flag = 0;int n = 0;for(int i = 1 ; i <= 7 ; i++){scanf("%d",&a[i]);if(a[i] == 1 && flag == 0){num = i;flag = 1;}if(a[i] == 1){n++;}}for(int i = 8 ; i <= 30 ; i++){a[i] = a[i-7];}long long int res = 0; // cout << k << "**" << n << endl;if(k <= 2*n){res = 99999999;for(int i = 1 ; i <= 7 ; i++){int z = 0;int z2 = k;for(int j = i ; j <= 30 ; j++){z++;if(a[j] == 1){z2--;}if(z2 == 0){break;}}if(z < res){res = z;}}printf("%lld\n",res);}else{ // cout << k << " " << n << endl;if((k-2*n)%n==0){res = (k-2*n)/n*7;k = 2*n;}else{res = (k-n)/n*7;k = (k-n)%n+n;} // cout << res << endl;int res2 = 999999;for(int i = 1 ; i <= 7 ; i++){int z = 0;int z2 = k;for(int j = i ; j <= 30 ; j++){z++;if(a[j] == 1){z2--;}if(z2 == 0){break;}}if(res2 >= z){res2 = z;}}printf("%lld\n",res+res2);}}return 0; }

F.Lazyland
題目：
鏈接：https://ac.nowcoder.com/acm/contest/7854/F
來源：牛客網

The kingdom of Lazyland is the home to n idlers. These idlers are incredibly lazy and create many problems to their ruler, the mighty King of Lazyland.
Today k important jobs for the kingdom (k ≤ n) should be performed. Every job should be done by one person and every person can do at most one job. The King allowed every idler to choose one job they wanted to do and the i-th idler has chosen the job ai.
Unfortunately, some jobs may not be chosen by anyone, so the King has to persuade some idlers to choose another job. The King knows that it takes bi minutes to persuade the i-th idler. He asked his minister of labour to calculate the minimum total time he needs to spend persuading the idlers to get all the jobs done. Can you help him?

題意：
有n個人，k個任務，每個人都有任務，都有勸說其完成其他任務的時間。你需要讓所有的K個任務都完成，沒被選的任務可以勸說其他人來完成。問完成所有任務需要最少的勸說時間是多少。

思路：
只需要記錄每個任務有多少個人選擇了，然后按照勸說時間從小到大排序，直接從頭遍歷一遍即可。

代碼：

#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){int k = 0, f = 1; char c = getchar();for(;!isdigit(c); c = getchar())if(c == '-') f = -1;for(;isdigit(c); c = getchar())k = k * 10 + c - '0';return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010 struct node {long long int x;long long int y; }a[MAXN]; long long int b[MAXN] = {0}; bool cmp(node x1,node x2) {return x1.y < x2.y; } int main() {long long int n , k;scanf("%lld %lld",&n,&k);long long int res = 0;long long int num = 0;for(int i = 0 ; i < n ; i++){scanf("%lld",&a[i].x);if(b[a[i].x] == 0){num++;}b[a[i].x]++;}for(int i = 0 ; i < n ; i++){scanf("%lld",&a[i].y);}sort(a,a+n,cmp); // for(int i = 0 ; i < n ; i++) // { // cout << a[i].x << " " << a[i].y << endl; // }if(num == k){printf("0\n");}else{num = k-num;for(int i = 0 ; i < n ; i++){if(num==0){break;}if(b[a[i].x]>1){res = res + a[i].y;b[a[i].x]--;num--;continue;}}printf("%lld\n",res);}return 0; }

I.Box
題目：
鏈接：https://ac.nowcoder.com/acm/contest/7854/I
來源：牛客網

Bella is working in a factory that produces boxes. All boxes are in a shape of rectangular parallelepipeds. A net of the corresponding parallelepiped is cut out of a flat rectangular piece of cardboard of size w ×h. This net is a polygon with sides parallel to the sides of the rectangle of the cardboard. The net is bent along several lines and is connected along the edges of the resulting parallelepiped to form a box. The net is bent only along the edges of the resulting box.

題意：
給出a,b,c,你想要得到的立方體的長寬高；給出w，h，你有的平面紙張的大小，問你是否可以剪下一張紙來拼接成你想要得到的立方體。

思路：
從他給出的11種展開圖可以看出，在長寬高都是1的情況下，只有三種紙張可以滿足條件，就是43，34，2*5.三種情況中找出三個展開圖，在長寬高改變的情況下，對應的紙張的w和h也在改變。對應的a,b,c有六種排列，每種排列對應三種展開圖，直接暴力枚舉就行了。

代碼：

#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){int k = 0, f = 1; char c = getchar();for(;!isdigit(c); c = getchar())if(c == '-') f = -1;for(;isdigit(c); c = getchar())k = k * 10 + c - '0';return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010 int a[MAXN]; int main() {int aa,bb,cc;int x , y;int w , h;cin >> a[1] >> a[2] >> a[3];cin >> w >> h;int flag = 0;aa = a[1];bb = a[2];cc = a[3];x = aa+aa+cc+cc;y = bb+cc+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+bb+cc;y = aa+2*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+cc;y = aa+3*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}aa = a[1];bb = a[3];cc = a[2];x = aa+aa+cc+cc;y = bb+cc+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+bb+cc;y = aa+2*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+cc;y = aa+3*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}aa = a[2];bb = a[1];cc = a[3];x = aa+aa+cc+cc;y = bb+cc+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+bb+cc;y = aa+2*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+cc;y = aa+3*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}aa = a[2];bb = a[3];cc = a[1];x = aa+aa+cc+cc;y = bb+cc+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+bb+cc;y = aa+2*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+cc;y = aa+3*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}aa = a[3];bb = a[1];cc = a[2];x = aa+aa+cc+cc;y = bb+cc+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+bb+cc;y = aa+2*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+cc;y = aa+3*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}aa = a[3];bb = a[2];cc = a[1];x = aa+aa+cc+cc;y = bb+cc+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+bb+cc;y = aa+2*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}x = aa+cc;y = aa+3*bb+cc;if(x<=w&&y<=h||x<=h&&y<=w){flag = 1;}if(flag == 1){cout << "Yes" << endl;}else{cout << "No" << endl;}return 0; }

菜的一批的我只寫出了三道題。
下面是補題：
A.Fractions
題目！：
鏈接：https://ac.nowcoder.com/acm/contest/7854/A
來源：牛客網

You are given a positive integer n.
Find a sequence of fractions ai / bi, i = 1…k (where ai and bi are positive integers) for some k such that:

題意：
給一個n，讓你構建一個序列，使序列滿足題目中給出的3個條件

思路：
來自dalao的證明
https://blog.csdn.net/qq_43235540/article/details/107830058?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param

代碼：

#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){int k = 0, f = 1; char c = getchar();for(;!isdigit(c); c = getchar())if(c == '-') f = -1;for(;isdigit(c); c = getchar())k = k * 10 + c - '0';return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010 int exgcd(ll a,ll b,ll &x,ll &y) {if(b==0){x=1;y=0;return a;}int r=exgcd(b,a%b,x,y);int tem=x;x=y;y=tem-a/b*y;return r; } int a[MAXN]; int main() {int n;scanf("%d",&n);int fac=0,nn=n,size=0;for(int i=2;i*i<=nn;++i){if(nn%i==0) {int tem = 1;while (nn % i == 0) {nn /= i;tem *= i;}if (!fac)fac = tem; //只要找到一個就行size++;}}if(nn>1)size++;if(size<=1)puts("NO");else {puts("YES");puts("2");int a=fac,b=n/fac,c=n-1; //此處開始套公式，ax+by=c ，最小正整數解x=x*c%( b/gcd(a,b))ll x,y; // 一定要用long long，不然在使用exgcd的時候會waint gcd=exgcd(a,b,x,y);int mod=b/gcd;x=(x*c/gcd %mod+mod)%mod; //防止負數y=(c-a*x)/b;printf("%d %d\n%d %d\n",x,n/a,y,n/b);}return 0; }

J.Connections
題目：
鏈接：https://ac.nowcoder.com/acm/contest/7854/J
來源：牛客網

Hard times are coming to Byteland. Quantum computing is becoming mainstream and Qubitland is going to occupy Byteland. The main problem is that Byteland does not have enough money for this war, so the King of Byteland Byteman 0x0B had decided to reform its road system to reduce expenses.
Byteland has n cities that are connected by m one-way roads and it is possible to get from any city to any other city using these roads. No two roads intersect outside of the cities and no other roads exist. By the way, roads are one-way because every road has a halfway barrier that may be passed in one direction only. These barriers are intended to force enemies to waste their time if they choose the wrong way.
The idea of the upcoming road reform is to abandon some roads so that exactly 2n roads remain. Advisers of the King think that it should be enough to keep the ability to get from any city to any other city. (Maybe even less is enough? They do not know for sure.) The problem is how to choose roads to abandon. Everyone in Byteland knows that you are the only one who can solve this problem.

題意：
給出所有的單向道路，現在想要每兩個點之間都可達，刪除一些邊，使只剩下2*n條邊，問可以刪掉哪些道路。

思路：
來自dalao的想法，做的時候雖然與之有些許交集，但錯過了。
進行兩邊dfs，第一遍從任意一個點pos跑，跑到不能跑為止。第二遍所有邊再建反向邊(重新開一個圖)，再對pos點dfs，這樣等價于除pos點以外的所有點向pos點跑。那些被訪問過的邊就是必須邊，剩下的就是把那些不需要的刪掉，直到滿足要求為止。

因為題目保證有解，那么dfs一遍一定是一棵樹，每一遍將被記錄下n-1條邊，因此兩次后最多記錄下2*n-2條邊。

代碼：

#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){int k = 0, f = 1; char c = getchar();for(;!isdigit(c); c = getchar())if(c == '-') f = -1;for(;isdigit(c); c = getchar())k = k * 10 + c - '0';return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010struct jj {int u,v,next; }w[100000],w1[100000]; int h[50000],h1[50000],visw[100000],vis[50000],numw,numw1; void insert(int u,int v) {w[numw].u=u;w[numw].v=v;w[numw].next=h[u];h[u]=numw++;w1[numw1].v=u;w1[numw1].next=h1[v];h1[v]=numw1++; } void dfs(int t) {int i;for(i=h[t];i!=-1;i=w[i].next){if(vis[w[i].v]==0){vis[w[i].v]=1;visw[i]=1;dfs(w[i].v);}} } void dfs1(int t) {int i;for(i=h1[t];i!=-1;i=w1[i].next){if(vis[w1[i].v]==0){vis[w1[i].v]=1;visw[i]=1;dfs1(w1[i].v);}} } int main() {int t,x,y,i,i1,num,n,m;scanf("%d",&t);while(t--){memset(h,-1,sizeof(h));memset(h1,-1,sizeof(h1));memset(visw,0,sizeof(visw)); //visw數組是記錄哪些邊被訪問過，哪些沒有被訪問過numw=0;numw1=0;scanf("%d %d",&n,&m);for(i=1;m>=i;i++){scanf("%d %d",&x,&y);insert(x-1,y-1);}memset(vis,0,sizeof(vis));dfs(0);memset(vis,0,sizeof(vis));dfs1(0);num=m;for(i=0;m>i&&num!=2*n;i++){if(visw[i]==0){num--;printf("%d %d\n",w[i].u+1,w[i].v+1);}}}return 0; }

總結

以上是生活随笔為你收集整理的2020牛客国庆DYA6的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。