加法和乘法
如果只有一个数，那么这个数是奇数则牛牛赢，否则牛妹赢。
如果不止一个数，那么假设有奇数个数，显然是牛妹赢。因为剩余2个数的时候，牛妹做最后一次操作，无论什么情况一定都能生成两个偶数（如果剩两个奇数就做加法，如果存在偶数就做乘法）。
假设有偶数个数，牛妹要做的就是让最后剩余2个偶数即可。牛牛每次最多可以消除一个偶数，牛妹每次最多可以生成一个偶数。所以如果初始状态的偶数不小于2个，则牛妹赢；否则牛牛赢。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll n;
cin>>n;
if(n==1){
ll x;
cin>>x;
if(x&1){
cout<<"NiuNiu";
}else{
cout<<"NiuMei";
}
cout<<endl;
return 0;
}else if(n==2){
ll x,y;
cin>>x>>y;
ll z1=x*y;
ll z2=x+y;
cout<<z1<<" "<<z2<<endl;
if((z1&1)||(z2&1)){
cout<<"NiuNiu"<<endl;
}else{
cout<<"NiuMei"<<endl;
}
return 0;
}else{
ll num=0;
for(ll i=1;i<=n;i++){
ll x;
cin>>x;
if(!(x&1)){
num++;
}
}
if(n&1){
cout<<"NiuMei"<<endl;
return 0;
}else{
if(num<=1){
cout<<"NiuNiu"<<endl;
}else{
cout<<"NiuMei"<<endl;
}
}
return 0;
}
return 0;
}
序列的美观度
通过p数组记录上一次某个数出现的位置，但是需要特殊处理一次还没有出现的情况，和dp中求最长上升子序列方法相似
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1000006];
ll dp[1000006];
ll p[1000006];
int main(){
ll n;
cin>>n;
for(ll i=1;i<=n;i++){
cin>>a[i];
}
dp[0]=0;
dp[1]=0;
p[a[1]]=1;
for(ll i=2;i<=n;i++){
if(p[a[i]]==0){
dp[i]=dp[i-1];
}else{
dp[i]=max(dp[i-1],dp[p[a[i]]]+1);
}
p[a[i]]=i;
}
cout<<dp[n];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
string s;
cin>>s;
string before="",after="";
int slen=s.length();
for(int i=0;i<slen;i++){
if(s[i]!='#') before+=s[i];
else break;
}
for(int i=s.length()-1;i>=0;i--){
if(s[i]!='#') after+=s[i];
else break;
}
// cout<<before<<" "<<after<<endl;
int blen=before.length(),alen=after.length();
for(int i=2;i<=n;i++){
string t;
cin>>t;
int tlen=t.length();
for(int j=0;j<tlen;j++){
if(t[j]=='#'){
break;
}
else{
if(j<blen){
if(t[j]!=before[j]){
cout<<0<<endl;
return 0;
}
}else{
before+=t[j];
blen++;
}
}
}
for(int j=tlen-1;j>=0;j--){
if(t[j]=='#') break;
else{
if(tlen-j-1<alen){
if(t[j]!=after[tlen-j-1]){
cout<<0<<endl;
return 0;
}
}else{
after+=t[j];
alen++;
}
}
}
}
cout<<-1<<endl;
return 0;
}
重力坠击
数据样例比较少，可以直接dfs
#include<bits/stdc++.h>
using namespace std;
int n,k,R;
int mp[20][20];
struct node{
int x,y,r;
}Node[20];
int a[5],b[5];
int dis(int x1,int y1,int x2,int y2){
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int num=0;
int maxx=-1;
void dfs(int deep){
if(deep>k){
int vis[20];
memset(vis,0,sizeof(vis));
for(int i=1;i<deep;i++){
for(int j=1;j<=n;j++){
if(vis[j]==0){
int res = dis(a[i],b[i],Node[j].x,Node[j].y);
if((Node[j].r+R)*(Node[j].r+R)>=res){
num++;
vis[j]=1;
}
}
}
}
maxx=max(maxx,num);
num=0;
}else{
for(int i=-7;i<=7;i++){
for(int j=-7;j<=7;j++){
if(mp[i+7][j+7]==0){
mp[i+7][j+7]=1;
a[deep]=i,b[deep]=j;
dfs(deep+1);
mp[i+7][j+7]=0;
}
}
}
}
}
int main(){
// int n,k,R;
cin>>n>>k>>R;
for(int i=1;i<=n;i++){
cin>>Node[i].x>>Node[i].y>>Node[i].r;
}
dfs(1);
cout<<maxx<<endl;
return 0;
}
