A. Computer Game
傳送門
題目描述
輸入描述
輸出描述
輸入樣例
4
3
000
000
4
0011
1100
4
0111
1110
6
010101
101010
輸出樣例
YES
YES
NO
YES
題目大意： 某遊戲中共有兩條道路，其中 1 表示障礙，0 表示可通過。每次可以橫、縱、斜向移動一格，判斷玩家是否能夠從左上角移動到右下角。
顯然，當某列兩行都為 1 時無論如何都不能通過，枚舉即可。
參考代碼
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int flag=1;
string a,b;
cin>>a>>b;
for(int i=0;i<n;i++){
if(a[i]=='1'&&b[i]=='1'){
cout<<"NO"<<endl;
flag=0;
break;
}
}
if(flag==1)
cout<<"YES"<<endl;
}
return 0;
}
C. Delete Two Elements
傳送門
題目描述
輸入描述
輸出描述
輸入樣例
4
4
8 8 8 8
3
50 20 10
5
1 4 7 3 5
7
1 2 3 4 5 6 7
輸出樣例
6
0
2
3
樣例解釋
題目大意： 從一個數組中删去兩個數，使其平均值（可能為小數）不變，問有幾種删法。
經過一番數學推理之後，可直接獲得等式 2 * sum = n ( x + y ) ；其中 sum 為原數組中所有元素之和，n 為元素個數，x、y 為符合要求将删去的數。
由于 x、y 都為整數，是以若 2 * sum / n 的餘數不為 0 時，答案為 0；
當餘數為 0 時，則符合要求的 x、y 相加後即為上述式子的商，在輸入數組時用 map 标記個數即可。若 x = y，需要注意特判。
參考代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int a[N];
int main(){
int t;
cin>>t;
while(t--){
int n,x;
ll ans=0,sum=0;
map<int,ll> mp;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
a[i]=x;
mp[x]++;
ans+=x;
}
if((2*ans)%n!=0){
cout<<"0"<<endl;
continue;
}
ans=(2*ans)/n;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(mp[a[i]]!=0&&mp[ans-a[i]]!=0){
if((2*a[i])==ans)
sum=sum+mp[a[i]]*(mp[a[i]]-1)/2;
else
sum=sum+mp[a[i]]*mp[ans-a[i]];
mp[a[i]]=mp[ans-a[i]]=0;
}
}
cout<<sum<<endl;
}
return 0;
}