春季每日一题第一周题解

• 你知道你的ABC吗(推理)
• 放养但没有完全放养(贪心)
• 牛年(模拟)
• 牛的学术圈 I(前缀和 + 技巧)
• 奶牛体操(思维 + 图论)

你知道你的ABC吗(推理)

题目链接

解题思路：
由于题面已经给出了A，B，C的大小关系。那么对于这几个数，我们知道A肯定是最小的，A+B+C是最大的，对于B，C的关系，我们假设B与A之间有一个数x，那么这个x要满足严格小于B，但是在剩余的数中我们是找不到满足条件的，因此，可以推出B是第二小的，那么我们由A + B + C 的值就可以得到C的值。

代码：

#include#includeusing namespace std;const int N = 10;int a[N];int n = 7;int main(){    for(int i = 0 ; i < n ; ++i)cin>>a[i];    sort(a,a+n);    for(int i = 0 ; i < 2 ; ++i)cout<<a[i]<<" ";    cout<<a[n-1] - a[0] - a[1]<<endl; // 发现也不用找，应为C一定存在，那么直接用A + B + C 的值 减去A 和B的值即可    return 0;}

放养但没有完全放养(贪心)

题目链接

解题思路：
这就是一个按位匹配，就是他听到的字母一定是有序（按照牛文）的，如果不是，那么就是新唱了一遍。
那么就是一直匹配就行了。

对于做法，我们库将听到的串，每匹配到一个就删去。那么当字符串长度为0的时候就匹配完全了。

代码：

#include#include#include#includeusing namespace std;const int N = 1010;string str , s;int main(){    cin>>str>>s;    int cnt = 0;    while(1){ cnt++; int n  = str.size(); for(int i = 0 ; i < n ; ++i )     if(str[i] == s[0])s.erase(s.begin()); if(s.size() == 0) break;    }    cout<<cnt<<endl;    return 0;}

牛年(模拟)

题目链接

解题思路：
pre 表明这个人在前边也就距离Bessie 更远 ， next 则是更近。我们对于每一个人存的都是距离Bessie 的距离。

1. 如何存储值，对于每个人对应的值和生肖我们可以用map来存。
2. 生肖刚开始的值，可以用map然后手动初始化，或者利用循环。
3. 对于pre我们有两种对于关系，一个是我的生肖就在你前边，那么我就不用再跨越一个年份去找了。同理next ，如果已经在后边了也是。

代码：

#include#include#include#include#includeusing namespace std;const int N = 1100000 , INF = 0x3f3f3f3f;map<string,int>st, ans; // ans 是 答案，也就是距离 ，st 是生肖的位置map<string,string>bk; //记录人对应的生肖int n ;string str ,a ,b , op ,anl ,bnl;string ss[14] = {"","Ox", "Tiger", "Rabbit", "Dragon", "Snake", "Horse", "Goat", "Monkey", "Rooster", "Dog", "Pig", "Rat"} ;void init(){    for(int i = 1 ; i <= 12 ; ++i) st[ss[i]] = i;}int main(){    init();    cin>>n;    ans["Bessie"] = 0 , bk["Bessie"] = "Ox";    while(n--){ for(int j = 1 ; j <= 8 ; ++j){     cin>>str;     if(j == 1) a = str; if(j == 8) b = str;     if(j == 4) op = str; if(j == 5) anl = str; } bk[a] = anl , bnl = bk[b]; if(op == "next")     {  if(st[anl] > st[bnl]) ans[a] = ans[b] - (st[anl] - st[bnl]);  else      ans[a] = ans[b] - ( 12 - st[bnl] + st[anl]);      } else{ // pre     if(st[anl] < st[bnl]) ans[a] = ans[b] + (st[bnl] - st[anl]);     else  ans[a] = ans[b] + (  st[bnl] + 12 -  st[anl] );  }    }    cout<<abs(ans["Elsie"])<<endl;    return 0;}

牛的学术圈 I(前缀和 + 技巧)

题目链接

题目大意
题目是要求一个最大的h，这个h满足在序列中的值大于等于h的个数至少有h个。同时由L个引用的机会。

解题思路
我们先暂时不管L个引用。对于前一个问题，我们可以对每一个数值用一个数组存下出现的个数。之后对这个数组求前缀和，那么我们就可以0(1)的复杂度，求出序列中值在[L,R]区间内的个数为s[R] - s[L-1].这样我们就解决了第一个问题。对于第二个问题，如果不限制对同一篇论文的引用次数的话，这题就复杂得多了。但是由于有了限制，那么对于h来说，哪些能通过后面这个引用满足条件呢，那就是与其差1的值的个数.如果num 小于 h，我们就看min(L,c[h-1]) >= h - num就可以了

• 为什么加min呢，是因为我们要求的需要的个数是，值为h-1个个数中我们能用L次引用提高上来的部分。

代码：

#include#include#includeusing namespace std;const int N = 1e5 + 10;int n , m;int s[N], a[N] , c[N];int main(){    cin>>n>>m;    for(int i = 1; i <= n ; ++i){ cin>>a[i]; c[a[i]]++;    }    for(int i = 1 ; i < N ;  ++i)s[i] = s[i-1] + c[i]; int h ;    for( h = 1;  h  ; ++h){ int num = s[N-1] - s[h-1]; if(num >= h)continue; if(min(m,c[h-1] ) >= h - num)continue; break;    }    cout<<h-1<<endl; return 0;}

奶牛体操(思维 + 图论)

题目链接

解题思路

在这里我们可以抽象，将排名之间的关系看成一条边。即每一次排名中，如果i在j前边，那么就建立一条i指向j的边。那么在所有关系都建立完之后，我们遍历所有的点对，如果i到j有边，但j到i没有边，那么就说明这么多次排名中j都没有在i前边，那么次数加1。

代码：

#include#include#includeusing namespace std;const int N = 110;int in[N] ,a[N];int n , m;bool st[N][N];int main(){    cin>>m>>n;    while(m--){ for(int i = 1 ; i <= n ; ++i)     cin>>a[i]; // 建立关系 for(int i = 1 ; i <= n ; ++i)     for(int j = i + 1 ; j <= n ; ++j)  st[a[i]][a[j]] = 1;    }    int ans = 0;    for(int i = 1 ; i <= n ; ++i) for(int j = 1 ; j <= n ; ++j){     if(st[i][j] && !st[j][i]) // 由于在建边的时候没有建立自己指向自己的所有不用特判  ans++ ; //如果i 指向j ，但j没有指向i，说明在这么多次排名中i都在j前边 }    cout<<ans<<endl;    return 0;}