A - Couple doubi
题意：桌上共有 k 个球，第i个球的值为 (1^i+2^i+...+(p-1)^i )mod pDouBiXp 和 他的女朋友 DouBiNan 轮流拿球，DouBiNan先拿，
所有的球都拿完后，谁手上球的值总和更大谁就赢，
已知 k,p，且p为素数，
若DouBiNan赢输出"YES",否则输出"NO"
分析：DouBiNan先拿，为了赢肯定先拿没有被拿的球中值最大的，
找规律得 每个球的值要么为 0，要么为某个的正数x，且每p-1个球有一个的值为x
那么如果值为x的球个数如果为奇数，则DouBiNan赢，否则赢不了
#include<stdio.h>
int main()
{
int p,n;
while(scanf("%d%d",&n,&p)!=EOF){
if((n/(p-1))%2)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
题意：有n台机器和m个任务，第i个任务需要xi时间去完成，且它的难度等级为yi
若第i个任务被完成，可获得收益 500*xi+2*yi
每台机器有一个最大工作时间和能完成的最大难度等级，
若某台机器要完成某任务，则机器的工作时间要不低于任务需要的时间，
机器的难度等级不低于任务的难度等级，
一台机器一天只能完成一次任务，且一个任务只能由一台机器完成
已知每台机器和每个任务的完成时间和难度等级，
求一天能完成的最多的任务数，在此前提下的最大收益
分析：贪心求解
收益只有完成的任务的x,y有关，且x，y越大，获得的收益越大
所以要优先完成x更大的任务，若x相等，要优先完成y大的任务
即任务要按x从大到小排序，若x相等则按y从大到小排序
任务的x按从大到小排序，再给任务匹配机器
当有多台机器符合x条件，那么要选择y满足条件的最小的y,
这样没被用的更大的y的机器，更可能符合完成其他任务
#include<stdio.h>
#include<algorithm>
#define N 100000
using namespace std;
struct stu{
int time,level;
}task[N+10],machine[N+10];
int cmp(stu a,stu b){
if(a.time==b.time)
return a.level>b.level;
return a.time>b.time;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++)
scanf("%d%d",&machine[i].time,&machine[i].level);
for(int i=1;i<=m;i++)
scanf("%d%d",&task[i].time,&task[i].level);
sort(machine+1,machine+1+n,cmp);
sort(task+1,task+1+m,cmp);
int j=1,cnt[105]={0},maxm=0;
long long ans=0;
for(int i=1;i<=m;i++){
while(j<=n&&task[i].time<=machine[j].time){
cnt[machine[j].level]++;
j++;
}
for(int k=task[i].level;k<=100;k++){
if(cnt[k]){
maxm++;
ans+=task[i].time*500+task[i].level*2;
cnt[k]--;
break;
}
}
}
printf("%d %I64d\n",maxm,ans);
}
return 0;
}
题意：已知昨天天气与今天天气状况的概率关系（wePro），和今天天气状态和叶子湿度的概率关系(lePro)
第一天为sunny 概率为 0.63,cloudy 概率 0.17,rainny 概率 0.2.
给定n天的叶子湿度状态，求这n天最可能的天气情况
分析：概率dp
设 dp[i][j] 表示第i天天气为j的最大概率，
pre[i][j]表示第i天天气最可能为j的前一天天气，
dp[i][j]=max(dp[i-1][k]+log(wePro[k][j])+log(lePro[j][lePos[i]])) (k=0,1,2 表示昨天的天气）
注：由于概率越乘越小，考虑精度原因，用log取对数
log(a*b*c) = log a + log b +log c
#include<stdio.h>
#include<string.h>
#include<math.h>
char Con[5][10]={"Dry","Dryish","Damp","Soggy"};
char We[5][10]={"Sunny","Cloudy","Rainy"};
double lePro[3][4]={0.6,0.2,0.15,0.05,
0.25,0.3,0.2,0.25,
0.05,0.10,0.35,0.50}; //叶子
double wePro[3][3]={0.5,0.375,0.125,
0.25,0.125,0.625,
0.25,0.375,0.375}; //天气
double init[3]={0.63,0.17,0.2};
double dp[55][3],pre[55][3];
int n,lePos[55];
void solve()
{
for(int i=0;i<3;i++)
dp[1][i]=log(init[i])+log(lePro[i][lePos[1]]);
for(int i=2;i<=n;i++){
for(int j=0;j<3;j++){ //今天天气
double maxp=-1e8;
int pos=0;
for(int k=0;k<3;k++){ //昨天天气
double temp=dp[i-1][k]+log(wePro[k][j])+log(lePro[j][lePos[i]]);
if(temp>maxp){
maxp=temp;
pos=k;
}
}
dp[i][j]=maxp;
pre[i][j]=pos;
}
}
}
int main()
{
int T;
scanf("%d",&T);
for(int k=1;k<=T;k++){
printf("Case #%d:\n",k);
scanf("%d",&n);
char con[10];
for(int i=1;i<=n;i++){
scanf("%s",con);
for(int j=0;j<4;j++)
if(strcmp(con,Con[j])==0){
lePos[i]=j;
break;
}
}
solve();
double maxp=-1e8;
int ans[55];
for(int i=0;i<3;i++)
if(dp[n][i]>maxp){
maxp=dp[n][i];
ans[n]=i;
}
for(int i=n-1;i>=1;i--)
ans[i]=pre[i+1][ans[i+1]];
for(int i=1;i<=n;i++)
printf("%s\n",We[ans[i]]);
}
return 0;
}
资料扩展：详情点此
本题属于 隐马尔可夫模型
马尔可夫模型:统计模型，每个状态只依赖于之前的状态
马尔可夫模型可用马尔可夫过程描述
我们就为上面的一阶马尔科夫过程定义了以下三个部分：
状态：晴天、阴天和下雨
初始向量：定义系统在时间为0的时候的状态的概率
状态转移矩阵：每种天气转换的概率
所有的能被这样描述的系统都是一个马尔科夫过程。
隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型，用来描述一个含有隐含未知参数的马尔可夫过程。
包含隐藏状态 （如：天气状态）和 可观状态（如：叶子的湿度）
可以观察到的状态序列和隐藏的状态序列是概率相关的
I - Turn the pokers
题意：有m张牌，初始状态都是正面朝下，现在要进行n次操作，
第i次操作要翻ai张牌,求n次操作后，牌的状态可能有多少种？
分析：牌只有两种状态，设面朝下为0，面朝上为1，则初始状态都为0
很显然每一张牌的状态只跟这张牌被翻的次数的奇偶性有关。
翻牌i次后1的个数的奇偶性一定与前i次翻牌的总张数 a1+a2+...+ai的奇偶性相同
（初始状态1的个数为0,是偶数，1.若翻偶数张牌，1的个数还是偶数
2.若翻奇数张，得到的还是奇数，
在第2种情况下若再翻奇数次，可能会翻奇数个0，偶数个1,或者偶数个0，奇数个1，
结果还是奇数，而两次翻牌张数和为偶加奇，也是奇数。。。可自行证明）
若终态有最少有min个1，最多有max个1，那么1的个数可能为 min,min+2,min+4,...,max
即牌的状态可能有 C(m,min)+C(m,min+2)+C(m,min+4)+...+C(m,max) 种
这样就转化为求min,max及组合数了
C(m,i)=m!/(i!*(m-i)!),因为最终要取余，而阶乘数太大存不了，还涉及到除法，
直接取余再除肯定不行（同余定理不适用于除法）
可以利用费马小定理解决：
由定理得：a^(p-1)≡1%p
则 a^(p-2)≡1/a%p
因为p很大，需要用快速幂取余来做
#include<stdio.h>
#define N 100000
#define mod 1000000009
#define LL long long
LL fact[N+10];
void init()
{
fact[0]=1;
for(int i=1;i<=N;i++)
fact[i]=fact[i-1]*i%mod;
}
LL powMod(LL a,LL b)
{
LL ans=1;
a%=mod;
while(b){
if(b%2)
ans=ans*a%mod;
b/=2;
a=a*a%mod;
}
return ans;
}
int main()
{
int n,m;
init();
while(scanf("%d%d",&n,&m)!=EOF){ //m张扑克，n次操作
int min1,max1,tempMin=0,tempMax=0; //1的最小最大个数
while(n--){
int x;
scanf("%d",&x);
//计算最少的1，要尽可能让1->0
if(x<=tempMin)
min1=tempMin-x;
else if(x<=tempMax){
if((x%2)==(tempMin%2))
min1=0;
else
min1=1;
}
else
min1=x-tempMax;
//计算最多的1,要尽可能让0->1
if(x<=m-tempMax)
max1=tempMax+x;
else if(x<=m-tempMin){
if((x%2)==((m-tempMin)%2))
max1=m;
else
max1=m-1;
}
else
max1=m-(x-(m-tempMin));
tempMin=min1;
tempMax=max1;
}
LL ans=0;
for(int i=min1;i<=max1;i+=2) //费马小定理
ans=(ans+(fact[m]*powMod(fact[i]*fact[m-i],mod-2))%mod)%mod;
printf("%I64d\n",ans);
}
return 0;
}
G - Xor
题意：有n个数 (a0,a1,..,an),
f(x)= 满足 b1 xor b2 xor ... xor bn = x 的个数 （0<=bi<=ai)
要进行m次操作
Q x, 求 f(x)
C x y，将第x个数 即 ax 修改为 y
分析：对于这种多查询多维护的题可以用线段树求解
线段树：
是一种擅长处理区间的数据结构。
对其的查找和维护的时间复杂度都是O(log n).
未优化的空间复杂度为 2n
若a0=100101 (二进制)
则b0 =0***** 或 1000** 或 100100 或 100101 （0<=b0<=a0）
将b中确定的位称为前缀，不确定的位（为0或1）称为后缀
则 线段树中结点需要 包含 前缀的值，后缀位数，及组成该形式的数的个数
前缀最大到 1000 (十进制)，后缀 最多为 10 ，可以用一个int存这两个信息
因为 10用 4位二进制就可表示，可以用后4位存后缀位数
组成该形式的数的个数 也可用 一个int即可
而b有多种可能形式，且个数未知
所以线段树的每个结点 可用 vector<pair<int,int> > 存储
子树根结点由左右孩子异或得到，将左右孩子可能的形式的数两两异或
可求子根结点，最终可得根结点（b1 xor b2 xor ... xor bn）每种情况的个数
求f(x) 即求根结点 每种情况能组成与x的相等的值的总和
每种情况是否能组成与x相等的值，即看前缀的值与x的前缀的值是否相等
#include<cstdio>
#include<vector>
#include<map>
#define N 20000
#define mod 1000000007
using namespace std;
int a[N+10],minlen;
vector<pair<int,int> > tree[2*N+10];
vector<pair<int,int> > creat_node(int val)
{
vector<pair<int,int> >temp;
for(int i=0;i<10;i++){ //val即a[i]最大1000，最多由10位二进制组成
if(val&(1<<i)){ //判断val第i位是否为1
int first=(((val>>i)^1)<<4)|i; //保留从第i位开始的前缀，并将第i位的1变成0
//且前缀后面添加4位，用来存后缀的位数，后缀位数最多为10，由四位二进制可表示
temp.push_back(make_pair(first,1));
//pair的second元素用来存组成上诉形式的数的个数
}
}
temp.push_back(make_pair(val<<4,1)); //与val相等，则前缀为val,后缀位数为0
return temp;
}
int Xor(int valL,int valR)
{
int lenL=valL&0xf,lenR=valR&0xf;
if(lenL>lenR){
swap(lenL,lenR);
swap(valL,valR);
}
valL>>=4;
valR>>=4;
valL>>=(lenR-lenL);
minlen=lenL;
return (valL^valR)<<4|lenR;
}
void pushUp(int node) //根据左右孩子求根节点
{
map<int,int> m;
tree[node].clear();
int lenL=tree[2*node].size();
int lenR=tree[2*node+1].size();
int cnt=0;
for(int i=0;i<lenL;i++){
for(int j=0;j<lenR;j++){
int first=Xor(tree[2*node][i].first,tree[2*node+1][j].first);
long long numL=tree[node*2][i].second;
long long numR=tree[node*2+1][j].second;
int second=numL*numR%mod*(1<<minlen)%mod;
if(m.find(first)==m.end()){
m[first]=cnt++;
tree[node].push_back(make_pair(first,second));
}
else{
int pos=m[first];
tree[node][pos].second=(tree[node][pos].second+second)%mod;
}
}
}
}
void build(int l,int r,int node) //建树
{
if(l==r){
tree[node]=creat_node(a[l]);
return ;
}
int mid=(l+r)>>1;
build(l,mid,node*2);
build(mid+1,r,node*2+1);
pushUp(node);
}
void update(int l,int r,int node,int pos,int val) //更新维护树
{
if(l==r){
tree[node]=creat_node(val);
return;
}
int mid=(l+r)>>1;
if(mid>=pos)
update(l,mid,node*2,pos,val);
else
update(mid+1,r,node*2+1,pos,val);
pushUp(node);
}
int query(int x,int node) //查找
{
int ans=0,num=tree[node].size();
for(int i=0;i<num;i++){
int first=tree[node][i].first;
int len=first&0xf;
first>>=4;
if(first==(x>>len))
ans=(ans+tree[node][i].second)%mod;
}
return ans;
}
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
while(m--){
char ope[3];
scanf("%s",ope);
if(ope[0]=='Q'){
int x;
scanf("%d",&x);
int ans=query(x,1);
printf("%d\n",ans);
}
else{
int x,y;
scanf("%d%d",&x,&y);
update(1,n,1,x+1,y);
}
}
}
return 0;
}