A.TD
签到题，直接输出即可。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const static void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
void solve(){
double n,m;
cin>>n>>m;
cout<<n/m<<endl;
}
signed main(){
fast_io();
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
B.你好，这里是牛客竞赛
字符串从头开始匹配即可。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const static void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
string s1="https://www.nowcoder.com";
string s2="https://ac.nowcoder.com";
string s3="www.nowcoder.com";
string s4="ac.nowcoder.com";
void solve(){
string a;
cin>>a;
if(a.substr(0,s1.size())==s1){
cout<<"Nowcoder"<<endl;
}else if(a.substr(0,s2.size())==s2){
cout<<"Ac"<<endl;
}else if(a.substr(0,s3.size())==s3){
cout<<"Nowcoder"<<endl;
}else if(a.substr(0,s4.size())==s4){
cout<<"Ac"<<endl;
}else{
cout<<"No"<<endl;
}
}
signed main(){
fast_io();
int T=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
C.逆序数
一个长度为n的排列，数与数之间不是正序数就是逆序数，即正序数和逆序数之和为n*(n-1)/2，所以题目的答案为n*(n-1)/2-k。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const static void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
void solve(){
int n,k;
cin>>n>>k;
cout<<(n-1)*n/2-k<<endl;
}
signed main(){
fast_io();
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
D.构造mex
s和n分别减去数的相加之和构造mex所需的个数再进行一步步分类讨论即可
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const static void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
void solve(){
int s,n,k;
cin>>s>>n>>k;
int sum=(k-1)*k/2;
s-=sum;
n-=k;
if(k==0){
if(n>s) cout<<"NO"<<endl;
else{
cout<<"YES"<<endl;
for(int i=1;i<n;i++) cout<<1<<' ';
s-=(n-1);
cout<<s<<endl;
}
return ;
}
if(s<0){
cout<<"NO"<<endl;
}else if(s==0){
if(n<0){
cout<<"NO"<<endl;
}else if(n==0){
cout<<"YES"<<endl;
for(int i=0;i<k;i++) cout<<i<<" \n"[i==k-1];
}else{
cout<<"YES"<<endl;
for(int i=0;i<k;i++) cout<<i<<' ';
for(int i=0;i<n;i++) cout<<0<<" \n"[i==n-1];
}
}else{
if(s==k&&n==1||n<=0||s==k&&k==1){
cout<<"NO"<<endl;
return ;
}
cout<<"YES"<<endl;
for(int i=0;i<k;i++) cout<<i<<' ';
for(int i=0;i<n;i++){
if(i==0){
if(s==k){
cout<<s-1<<' ';
cout<<1<<' ';
i++;
}else cout<<s<<' ';
}else cout<<0<<' ';
}
cout<<endl;
}
}
signed main(){
fast_io();
int T=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
E.小红的X型矩阵
首先将n×n的矩阵拓展为2n×2n的矩阵，
利用类似于八皇后问题的做法，用(y-x+n)%n来标记正对角线，(x+y)%n来标记反对角线，开数组s1,s2来记录对角线上的1的个数。
操作次数为总的1的个数减去对角线上1的个数加上对角线上0的个数
关于对角线上0的个数的计算：对角上的点的个数(奇数为2n-1，偶数为2n)减去对角线上1的个数(需要注意的是当n为奇数时，正对角线和反对角线交于一个点，如果这个点是1，则会重复计算，需要减去1)。
枚举左上角的点，操作次数取最小值即可。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const static void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
const int N=2010;
const int inf=0x3f3f3f3f3f3f3f3f;
vector<vector<int>>a(N,vector<int>(N));
vector<int>s1(N),s2(N);
int tot,ans=inf;
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
tot+=a[i][j];
}
}
auto cal1=[&](int x,int y){ return (x-y+n)%n; };
auto cal2=[&](int x,int y){ return (x+y)%n; };
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]){
s1[cal1(i,j)]++;//正对角线
s2[cal2(i,j)]++;//反对角线
}
}
}
//枚举左上角
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int t1=cal1(i,j);
int t2=cal2(i,j+n-1);
int res=s1[t1]+s2[t2]-n%2*(a[(i+n/2)%n][(j+n/2)%n]==1);//特判奇数并且俩条对角线交点是1
ans=min(ans,tot-res+n*2-n%2-res);
}
}
cout<<ans<<endl;
}
signed main(){
fast_io();
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
F.小红的数组回文值
用i和j枚举数组的元素，当a[i]和a[j]不同时，才会对答案有贡献。对于下标i和下标j之间的元素选与不选有2的j-i-1次方种状态，对于下标i之前的元素有i-1个，下标j之后的元素有n-j个,俩边取相同个数，最多能min(i-1,n-j)个，从0枚举到min(i-1,n-j)过于麻烦，可以利用范德蒙德卷积这一公式来优化这一操作。题目的答案即为所有a[i]≠a[j]时的贡献值之和。
关于范德蒙德卷积 链接https://oi-wiki.org/math/combinatorics/vandermonde-convolution/
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'
const static void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
T res {1};
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
} // 快速幂
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
} // 取模乘
template<i64 P>
struct MInt {
i64 x;
constexpr MInt() : x {0} {}
constexpr MInt(i64 x) : x {norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) {
Mod = Mod_;
}//只有P<=0, setMod才生效
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
if (getMod() < (1ULL << 31)) {
x = x * rhs.x % int(getMod());
} else {
x = mul(x, rhs.x, getMod());
}
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
friend constexpr bool operator<(MInt lhs, MInt rhs) {
return lhs.val() < rhs.val();
}
};
template<>
i64 MInt<0>::Mod = 998244353; //只有P<=0, Mod才生效
constexpr int P = 1e9+7; //在这设置要用的模数
using Z = MInt<P>;
//------取模机------//
//----计算组合数----//
struct Comb {
int n;
std::vector<Z> _fac; //阶乘
std::vector<Z> _invfac; //阶乘的逆元
std::vector<Z> _inv; //数字的逆元
Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
Comb(int n) : Comb() {
init(n);
}
void init(int m) {
m = std::min<i64>(m, Z::getMod() - 1);
if (m <= n) return;
_fac.resize(m + 1);
_invfac.resize(m + 1);
_inv.resize(m + 1);
for (int i = n + 1; i <= m; i++) {
_fac[i] = _fac[i - 1] * i;
}
_invfac[m] = _fac[m].inv();
for (int i = m; i > n; i--) {
_invfac[i - 1] = _invfac[i] * i;
_inv[i] = _invfac[i] * _fac[i - 1];
}
n = m;
}
Z fac(int m) {
if (m > n) init(2 * m);
return _fac[m];
}
Z invfac(int m) {
if (m > n) init(2 * m);
return _invfac[m];
}
Z inv(int m) {
if (m > n) init(2 * m);
return _inv[m];
}
Z C(int n, int m) {
if (n < m || m < 0) return 0;
return fac(n) * invfac(m) * invfac(n - m);
}
Z A(int n, int m) {
if (n < m || m < 0 ) return 0;
return fac(n) * invfac(n - m);
}
} comb;
//----计算组合数----//
const int mod=1e9+7;
int ksm(long a,long b){
long long res=1%mod;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int inv(int x){ return ksm(x,mod-2); }
void solve(){
int n;
Z ans=0;
cin>>n;
vector<int>a(n+1);
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++){
if(a[i]!=a[j]){
int res=min(i-1,n-j);//左边和右边各取相同个数的数最多能取几个
ans+=ksm(2,j-i-1)*comb.C(i-1+n-j,res);
//中间的数字随便取有2^j-i-1种状态
//范德蒙德卷积
}
}
}
cout<<ans<<endl;
}
signed main(){
fast_io();
int T=1;
//cin>>T;
while(T--) solve();
return 0;
}
京公网安备 11010502036488号