A
只要路途不被堵住就行，也就是只要同一列不都是障碍物就行
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[]={-1,0,1,0,1,1,-1,-1},dy[]={0,1,0,-1,1,-1,1,-1};
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const int N = 2e5+5,M = 2e5+5;
ll n,m;
void solve()
{
cin>>n;
string a,b;
cin>>a>>b;
for(int i=0;i<n;i++)
{
if(a[i]==b[i] and a[i]=='1')
{
cout<<"NO\n";
return ;
}
}
cout<<"YES\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int _;
cin>>_;
while(_--)
{
solve();
}
return 0;
}
也可以dfs写，不过在这个题显得有点麻烦了
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[]={-1,0,1,0,1,1,-1,-1},dy[]={0,1,0,-1,1,-1,1,-1};
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const int N = 1e5+5,M = 2e5+5;
int n,m,k;
char g[3][105];
bool vis[3][105];
bool dfs(int x,int y)
{
vis[x][y] = true;
if(x==2 and y==n) return true;
for(int i=0;i<8;i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<1 or nx>2 or ny<1 or ny>n) continue;
if(vis[nx][ny] or g[nx][ny]=='1') continue;
return dfs(nx,ny);
}
return false;
}
void solve()
{
cin>>n;
memset(vis,false,sizeof vis);
for(int i=1;i<=2;i++)
cin>>g[i]+1;
if(dfs(1,1)) cout<<"YES\n";
else cout<<"NO\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int _;
cin>>_;
while(_--)
{
solve();
}
return 0;
}
B
暴力做法，枚举两列，看这两列是否符合条件。
如果存在符合题目条件的两列，就为YES，否则为NO
如何判断是否两列符合条件：
首先两列中每列的1的个数都大于等于n的一半。
然后我们可以这么想，如果两列各有一半为1 。
n = 6
第i列：111000
第j列：000111
如果再有0变为1，两列选取的结果可能改变，也可能不改变。
第i列：111100
第j列：000111
的结果就没有改变，因为第二列必须选择那三个1
111100
001111
的结果就有两种情况，是可变的。
总结下来，只要满足有两列的对应位的或运算都为1，那么就满足条件。如果存在或运算为0，就不满足条件。
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[]={-1,0,1,0,1,1,-1,-1},dy[]={0,1,0,-1,1,-1,1,-1};
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const int N = 1e5+5,M = 2e5+5;
int n,m,k;
int g[1005][6];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=5;j++)
cin>>g[i][j];
for(int i=1;i<=5;i++)
{
for(int j=i+1;j<=5;j++)
{
bool is = true;
int cnt1 = 0,cnt2 = 0;
for(int k=1;k<=n;k++)
{
if(g[k][i]==1) cnt1++;
if(g[k][j]==1) cnt2++;
if(!(g[k][j]|g[k][i])) is = false;
}
if(is and cnt1>=n/2 and cnt2 >= n/2)
{
cout<<"YES\n";
return ;
}
}
}
cout<<"NO\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int _;
cin>>_;
while(_--)
{
solve();
}
return 0;
}
C
思路：
要满足删除掉两个元素后，平均值不改变，也就是求得
a
i
+
a
j
=
2
?
k
a_i+a_j = 2*k
ai?+aj?=2?k
使用map记录某个数出现的次数
访问到每个数时，就更新下map
当我们访问到一个数时，我们把结果加上
2
?
k
?
a
[
i
]
2*k-a[i]
2?k?a[i]出现的个数，就是访问到的这个数与另外的数能够组成的数对个数。
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[]={-1,0,1,0,1,1,-1,-1},dy[]={0,1,0,-1,1,-1,1,-1};
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const int N = 2e5+5,M = 2e5+5;
int n,m;
double a[N];
void solve()
{
cin>>n;
map<double,int>mp;
double sum = 0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum += a[i];
}
ll res = 0;
double k = sum*2/n;
for(int i=1;i<=n;i++)
{
res += mp[k-a[i]];
mp[a[i]]++;
}
cout<<res<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int _;
cin>>_;
while(_--)
{
solve();
}
return 0;
}
D
题意：
n个题目，每个题目有两个参数
a
i
,
b
i
a_i,b_i
ai?,bi?，不会存在相同的两个题目（即两个参数都一样），现需要选择3道题目，要求至少满足两个条件的一个：1.三个题目的
a
i
a_i
ai?都不一样 ，2.三个题目的
b
i
b_i
bi?都不一样
思路：
我们从整体来分析，用全部的个数减去不满足情况的个数
C
n
3
C_n^3
Cn3?是从n种选3种的情况，也就是全部的情况，但是其中包含了不满足条件的情况。
接下来计算不满足条件的情况：
必须是两个参数都出现相同的数的情况
我们统计每个数出现的个数，我们 计算每一个问题对 不满足情况的个数 的贡献。
也就是对于每一个问题，它对不满足条件的贡献就是这个问题第一个参数
a
i
a_i
ai?出现的个数减去1（要除去本身）乘上这个问题第二个参数
b
i
b_i
bi?的出现的个数减去1（除去本身），即
(
c
a
[
a
[
i
]
]
?
1
)
?
(
c
b
[
b
[
i
]
]
?
1
)
(ca[a[i]]-1)*(cb[b[i]]-1)
(ca[a[i]]?1)?(cb[b[i]]?1)
因为题目中有一句话，不会出现相同的问题。
随便假设一个例子
a b
a c
d b
对于第一个问题，与a相同的个数有2，除去本身，就是减一，这些与第一个问题第一个参数相同(即a)的问题的第二个参数一定不会等于b，同理第二个参数相同的问题的第一个参数也一定不相等。
就类似排列组合一样，与第一个参数相同的问题选择一个，与第二个参数相同的问题选择一个，一共三个问题，除去本身之后个数相乘就是对于一个问题的相应贡献。
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[]={-1,0,1,0,1,1,-1,-1},dy[]={0,1,0,-1,1,-1,1,-1};
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const int N = 2e5+5,M = 2e5+5;
ll n,m;
int a[N],b[N];
int ca[N],cb[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) ca[i] = cb[i] = 0;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
ca[a[i]]++;
cb[b[i]]++;
}
ll res = n*(n-1)*(n-2)/6;
for(int i=1;i<=n;i++)
res -= (ll)(ca[a[i]]-1)*(cb[b[i]]-1);
cout<<res<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int _;
cin>>_;
while(_--)
{
solve();
}
return 0;
}
往期优质文章推荐
|