A. Polycarp and the Day of Pi
做一个匹配即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int main() {
ios::sync_with_stdio(false);
string p="31415926535897932384626433832795028841971";
int T;
cin>>T;
while(T--)
{
string in;
cin>>in;
int ans=0;
for(int i=0;i<30&&i<p.length()&&i<in.length();i++)
{
if(p[i]==in[i])
ans++;
else
break;
}
cout<<ans<<'\n';
}
return 0;
}B. Taisia and Dice
根据题意知道拿走的那个最大值为s-r，可以先将最大值输出，剩下的r剩余数平分，再补上余数即可.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n,s,r;
cin>>n>>s>>r;
int m=s-r;
cout<<m<<' ';
for(int i=1;i<=r%(n-1);i++)
cout<<r/(n-1)+1<<' ';
for(int i=r%(n-1)+1;i<n;i++)
cout<<r/(n-1)<<' ';
cout<<'\n';
}
return 0;
}C. Premutation
我是把第一组输入当做默认数组，在剩下的输入中寻找默认数组中未出现的数m的位置site.
将site更新为其最大值，发现在此值之前的位置都可以按默认数组中的顺序输出，然后接一个m，后面接上剩余的默认数组中的数.
如果site为1，那么m应放在默认数组之前.
如果site为n-1，那么需要判断一下site是否一直为n-1，如果是，那么m在最后，如果不是，正常输出.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
const int N=105;
int a[N][N];
int o[N];
int vis[N];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
memset(vis,false,sizeof(vis));
memset(o,0,sizeof(o));
memset(a,0,sizeof(a));
int n;
cin>>n;
for(int i=1;i<n;i++)
{
cin>>o[i];
vis[o[i]]=true;
}
int m=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
m=i;
break;
}
}
int site=0;
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
if(a[i][j]==m)
{
site=max(site,j);
break;
}
}
}
if(site==1)
{
cout<<m<<' ';
for(int i=1;i<n;i++)
cout<<o[i]<<' ';
cout<<'\n';
}
else if(site==n-1)
{
bool flag=false;
for(int i=1;i<n;i++)
{
if(a[i][n-1]!=m)
{
flag=true;
break;
}
}
if(!flag)
{
for(int i=1;i<n;i++)
cout<<o[i]<<' ';
cout<<m<<'\n';
}
else
{
for(int i=1;i<site;i++)
cout<<o[i]<<' ';
cout<<m<<' ';
for(int i=site;i<n;i++)
cout<<o[i]<<' ';
cout<<'\n';
}
}
else
{
for(int i=1;i<site;i++)
cout<<o[i]<<' ';
cout<<m<<' ';
for(int i=site;i<n;i++)
cout<<o[i]<<' ';
cout<<'\n';
}
}
return 0;
}D. Matryoshkas
可以想到将每个数出现的次数当成纵坐标，横坐标为每个数，考虑这个生成的直方图，只需要一层一层地拿掉所有的高度即可.
因为 map优化.
一开始想的是用类似括号匹配一样的方法，但这样会有多重循环，最差情况会有平方级复杂度，会炸掉.
发现可以只考虑上坡，下坡根本不用管.
只需要统计连续的上坡(严谨来说是不下坡)的区间，计算高度即可.
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
const int N=2e5+5;
int a[N];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int ans=0;
map<int,int>mp;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
mp[a[i]]++;
}
auto it=mp.begin(),itt=mp.begin();
it++;
ans+=itt->second;
while(it!=mp.end())
{
if(it->first>itt->first+1)
{
ans+=it->second;
it++,itt++;
continue;
}
if(it->second>itt->second)
{
ans+=it->second-itt->second;
}
it++,itt++;
}
cout<<ans<<'\n';
}
return 0;
}耗时124ms，占用内存7200KB.
后来去看其他人提交的代码，有很简洁的，下面贴一份.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
const int N=2e5+5;
int a[N];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int ans=0;
sort(a+1,a+1+n);
map<int,int> mp;
for(int i=1;i<=n;i++)
{
if(!mp[a[i]-1])
{
ans++;
mp[a[i]]++;
}
else
{
mp[a[i]-1]--;
mp[a[i]]++;
}
}
cout<<ans<<'\n';
}
return 0;
}耗时156ms，占用内存13500KB.
E. Vlad and a Pair of Numbers
首先可以发现x为奇数的时候不行(转为二进制后末尾的1无法处理).
x为偶数时，构造
防止
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define lowbit(x) ((x)&-(x))
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
ll x;
cin>>x;
if(x%2!=0)
{
cout<<-1<<'\n';
continue;
}
ll a=x+(x>>1);
ll b=(x>>1);
ll tmp=a^b;
if(tmp==x)
cout<<a<<' '<<b<<'\n';
else
cout<<-1<<'\n';
}
return 0;
}