A题 牛牛浇树
可以使用差分,在a[l]++,在a[r+1]--,最后遍历一遍统计就行了。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 返回m天后高度为奇数的树的数量 * @param n int整型 * @param m int整型 * @param l int整型vector * @param r int整型vector * @return int整型 */ int a[500000]; int oddnumber(int n, int m, vector<int>& l, vector<int>& r) { for(int i=0;i<m;i++) { a[l[i]]++; a[r[i]+1]--; } for(int i=1;i<=n;i++) a[0]=m; for(int i=1;i<=n;i++) a[i]+=a[i-1]; int ans=0; for(int i=1;i<=n;i++) { if(a[i]&1) ans++; } return ans; } };
B题 挑选方案问题
我写了一个dfs打表找规律,发送n=3时 结果为 10. n等于4时 结果为15,符合二次函数sum=1/2*nn+3/2*n+1
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return long长整型 */ long long wwork(int n) { unsigned long long m = n; unsigned long long k =(( (m) * (m) + 3 * m))/2+1; return k; } };
C题 大逃离
先排序,每个点的概率为 因为有模运算,要采用逆元。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @param k int整型 * @param Point int整型vector * @return int整型vector */ typedef long long ll; long long a[400000]; long long md = 1000000007; struct node { long long data; int id; } b[400000]; static int cmp(node x, node y) { return x.data < y.data; } long long c[400000]; ll ksm(ll x, ll y) { ll sum = 1; while (y) { if (y & 1) sum = sum * x%md; y >>= 1; x = x * x%md; } return sum; } long long cxk(int x,int y) { return a[y]*ksm(a[x]*a[y-x]%md,md-2)%md; } vector<int> city(int n, int k, vector<int> &Point) { // write code here a[0] = 1; for (int i = 1; i <= 200000; i++) { a[i] = a[i - 1] * i % md; } for (int i = 0; i < n; i++) { b[i + 1].data = Point[i]; b[i + 1].id = i + 1; } sort(b + 1, b + 1 + n, cmp); for (int i = 1; i <= n; i++) { if (i < k) { c[b[i].id]=0; } else { c[b[i].id]=cxk(k-1,i-1)*ksm(cxk(k,n),md-2)%md; } } vector<int>f; for(int i=1;i<=n;i++) f.push_back(c[i]); return f; } };