J-T1 power
//T1
#include<cstdio>
using namespace std;
int n;
int main(){
scanf("%d",&n);
if(n&1){//判断奇数
printf("-1");
return 0;
}
for(int i=23;i>=1;--i)//log(2,1e7)≈23.3
if(n&(1<<i))
printf("%d ",(1<<i));
return 0;
}
J-T2 live
//T2
#include<cstdio>
#include<algorithm>
using namespace std;
int bucket[601],n,w,sum,tot,x;
int main(){
scanf("%d%d",&n,&w);
for(int i=1;i<=n;++i){
scanf("%d",&x);
++bucket[x];//桶记录
tot=bucket[600],sum=max(1,i*w/100);//tot记录当前人数，sum记录目标人数
for(int j=599;j>=0;--j){//x∈[0,600]
tot+=bucket[j];
if(tot>=sum){
printf("%d ",j);
break;//进行下一轮读入
}
}
}
return 0;
}
J-T3 expr
//T3
#include<cstdio>
#include<stack>
using namespace std;
struct node{
bool res;//res:记录遍历到此节点的返回值
bool flag;//flag:记录是否取反
int op;//op:为正代表变量的下标,-2代表and,-3代表or
int ls,rs;//ls:左子节点,rs:右子节点
}expr[1000011];//往大里开
bool v[100011];//v[]记录每个变量的值
bool unwork[100011];//unwork[]记录每个变量的改变是否会影响结果
stack<int> s;//stack[]用于读入表达式的同时建树
int n,q;//题目中的变量
int tot;//tot记录操作符和变量的总个数(除not外)
void mark(int i){//用于标记i及i的子节点
if(i==-1)//无子节点退出
return;
if(expr[i].op>0 && unwork[expr[i].op])//若该节点已被标记，则该节点的子节点一定已被标记，无需再一次进行标记
return;
if(expr[i].op>0)//变量要进行标记，并且不必再递归
unwork[expr[i].op]=true;//标记
else{//不是变量要递归
mark(expr[i].ls);//对左子树下的节点进行标记
mark(expr[i].rs);//对右子树下的节点进行标记
}
}
int main(){
char c;
while((c=getchar())>=32){//输入共一行,读到<32的字符就结束
if(c==32)//空格跳过
continue;
if(c=='x'){//变量
int x;
scanf("%d",&x);
expr[++tot].op=x;//记录变量下标
expr[tot].ls=expr[tot].rs=-1;//无左右子树
s.push(tot);//自己入栈
}
if(c=='!')
expr[s.top()].flag^=1;//对not对参数进行标记
if(c=='&'){
expr[++tot].op=-2;//记为and
expr[tot].ls=s.top();//记录栈顶为左子树
s.pop();//栈顶出栈
expr[tot].rs=s.top();//记录栈顶为右子树
s.pop();//栈顶出栈
s.push(tot);//自己入栈
}
if(c=='|'){
expr[++tot].op=-3;//记为or
expr[tot].ls=s.top();//记录栈顶为左子树
s.pop();//栈顶出栈
expr[tot].rs=s.top();//记录栈顶为右子树
s.pop();//栈顶出栈
s.push(tot);//自己入栈
}
}
scanf("%d",&n);
for(int i=1;i<=n;++i){
while((c=getchar())<=32);//去空格
v[i]=c-'0';
}
for(int i=1;i<=tot;++i){//对每个子节点进行赋值
if(expr[i].op>0)//变量
expr[i].res=v[expr[i].op],expr[i].res^=expr[i].flag;
if(expr[i].op==-2){//and
bool res1=expr[expr[i].ls].res;//记录左子树的值
if(!res1)//为0则对右子树标记为对结果无影响
mark(expr[i].rs);
bool res2=expr[expr[i].rs].res;//对右子树进行相同的操作
if(!res2)
mark(expr[i].ls);
expr[i].res=res1&res2;//结果
expr[i].res^=expr[i].flag;//取反
}
if(expr[i].op==-3){//or
bool res1=expr[expr[i].ls].res;//记录左子树的值
if(res1)//为1则对右子树标记为对结果无影响
mark(expr[i].rs);
bool res2=expr[expr[i].rs].res;//对右子树进行相同操作
if(res2)
mark(expr[i].ls);
expr[i].res=res1|res2;//结果
expr[i].res^=expr[i].flag;//取反
}
}
scanf("%d",&q);
while(q--){
int x;
scanf("%d",&x);
printf("%d
",unwork[x]?expr[tot].res:!expr[tot].res);//如果对结果无影响直接输出当前结果，否则输出取反的结果
}
}
J-T4 number
//T4
#include<cstdio>
using namespace std;
typedef long long LL;
const LL INF=-(1e10);//数据范围内无穷小(1e3*1e3*1e4)，要用LL记录
int n,m,num[1001][1001];
LL f[1001][1001][2];
//记忆化搜索，f[i][j][k]记录搜索至[i][j]时搜索的上一步为k的值(k:0->上,1->下)
LL max(LL x,LL y,LL z){return z==0?(x>y?x:y):max(max(x,y,0),max(y,z,0),0);}
//自己写的三个LL比大小
LL dfs(int x,int y,int op){
if(x<1 || x>n || y<1 || y>m)//边界判定
return INF;
if(f[x][y][op]!=INF)//由于是逆向搜索，搜到过的一定是最优解，不必用vis[][]记录是否已访问
return f[x][y][op];
return f[x][y][op]=max(dfs(x+(op*2-1),y,op),dfs(x,y-1,0),dfs(x,y-1,1))+num[x][y];
//Line 15 等价于下面多行注释的代码段
/*
if(op==0)//上一步为向上，这一步不能向下只能向上
f[x][y][op]=max( dfs(x-1,y,0) , dfs(x,y-1,0) , dfs(x,y-1,1) );//如果从左边来，就必须判断两个方向
if(op==1)//上一步为向下，这一步不能向上只能向下
f[x][y][op]=max( dfs(x+1,y,1) , dfs(x,y-1,0) , dfs(x,y-1,1) );//同理
return f[x][y][op];
*/
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
scanf("%d",&num[i][j])
f[i][j][0]=f[i][j][1]=INF;//先记为无穷小
}
f[1][1][0]=f[1][1][1]=num[1][1];//初始化
printf("%lld",dfs(n,m,0));//如果写成dfs(n,m,1)则无法搜到(n-1,m)，但无论如何一定会搜到(n,m-1)
return 0;
}
S-T1 julian
//T1
#include<cstdio>
using namespace std;
int D[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};//记录每个月的天数(其实因为特判2月可以不计)
struct pair{int x,y;};
pair date(int x,bool rn){//返回一年内的第x天是几月几日(rn表示是否为闰年)(x=0->1月1日)
int t=0;//t记录模拟到第t天
pair res;//用pair记录,其中x表示月份,y表示日期
res.x=res.y=1;//初始化为1月1日
while(t!=x){//懒得打数学算法,一年内用模拟即可
t++;
res.y++;//天数++
if(res.y>=29){//天数大于29时就有可能到下个月
if(res.x==2){//2月的特判
if(!rn && res.y==29){//不是闰年,只有28天
res.x=3,res.y=1;//3月1日
}
if(rn && res.y==30){//是闰年,有29天
res.x=3,res.y=1;//3月1日
}
}
else{
if(res.y>D[res.x]){//超过月份边界
res.x++;res.y=1;//下一个月1日
}
}
}
}
return res;
}
void g(long long x){//读入的x为儒略历(本函数中的y均表示年份)
if(x<=1721423){//-1/12/31
int y=-4713;
y+=4*(x/1461);//4年一闰年,一周期共365*4+1=1461天
x%=1461;
if(x<366){//该周期的第一年是闰年
printf("%d %d %d BC
",date(x,true).y,date(x,true).x,-y);
return;//记得返回,不然可能TLE
}
else{
x--;//去掉闰年多的一天,看成平年
y+=x/365;
x%=365;
printf("%d %d %d BC
",date(x,false).y,date(x,false).x,-y);
return;
}
}
if(x>=1721424 && x<=2299160){//1/1/1~1582/10/4
x-=1721424;//从1/1/1开始计算
int y=1;//年份初始化为1
y+=4*(x/1461);//同上,使用格里高利历前依然为4年一闰年
x%=1461;//同上
if(x<1095){//这次是前3年是平年
y+=x/365;
x%=365;
printf("%d %d %d
",date(x,false).y,date(x,false).x,y);
return;
}
else{
y+=3;//去掉前3年
x-=1095;//同上
printf("%d %d %d
",date(x,true).y,date(x,true).x,y);
return;
}
}
if(x>=2299161 && x<=2305813){//1582/10/15~1600/12/31(这部分直接带入比较麻烦,进行特殊处理)
if(x<=2299238){//1582/10/15~1582/12/31
x-=2299161;//从1582/10/15开始
x+=15;//从1582/10/1开始
if(x>=1 && x<=31){//1582/10/1~31
printf("%d 10 1582
",x);
return;
}
if(x>=32 && x<=61){//1582/11/1~31
printf("%d 11 1582
",x-31);
return;
}
if(x>=62 && x<=92){//1582/12/1~31
printf("%d 12 1582
",x-61);
return;
}
}
if(x>=2299239 && x<=2299603){//1583/1/1~1583/12/31
x-=2299239;//从1583/1/1开始
printf("%d %d 1583
",date(x,false).y,date(x,false).x);
return;
}
if(x>=2299604 && x<=2299969){//1584/1/1~1584/12/31
x-=2299604;//从1584/1/1开始
printf("%d %d 1584
",date(x,true).y,date(x,true).x);//闰年!!
return;
}
if(x>=2299970 && x<=2305813){//1585/1/1~1600/12/31
x-=2299970;//从1585/1/1开始
int y=1585;//年份初始化为1585
y+=4*(x/1461);//四年一周期
x%=1461;//同上
if(x<1095){//前三年为平年
y+=x/365;
x%=365;
printf("%d %d %d
",date(x,false).y,date(x,false).x,y);
return;
}
else{//第四年(闰年)
y+=3;
x-=1095;
printf("%d %d %d
",date(x,true).y,date(x,true).x,y);
return;
}
}
}
if(x>=2305814){//1601/1/1~..
x-=2305814;//从1601/1/1开始
long long y=1601;//初始化年份为1601
y+=400*(x/146097);//400年为1周期,共365*400+24*4+1=146097
x%=146097;//同上
if(x<=109572){//前300年
y+=100*(x/36524);//100年为1周期
x%=36524;//同上
if(x<=35064){//前96年
y+=4*(x/1461);//4年为1周期
x%=1461;//同上
if(x<=1095){//前3年为平年
y+=x/365;
x%=365;
printf("%d %d %lld
",date(x,false).y,date(x,false).x,y);
return;
}
else{//第4年(闰年)
y+=3;
x-=1095;
printf("%d %d %lld
",date(x,true).y,date(x,true).x,y);
return;
}
}
else{//第97~100年(由于是前300年,此处的第100年是平年)
y+=96;//加上前面的96年
x-=35064;//去掉前面的96年
y+=x/365;
x%=365;
printf("%d %d %lld
",date(x,false).y,date(x,false).x,y);
return;
}
}
else{//第301~400年
y+=300;//加上前面的300年
x-=109572;//去掉前面的300年
y+=4*(x/1461);//4年1周期
x%=1461;//同上
if(x<=1095){//前3年为平年
y+=x/365;
x%=365;
printf("%d %d %lld
",date(x,false).y,date(x,false).x,y);
return;
}
else{//第4年(闰年)
y+=3;
x-=1095;
printf("%d %d %lld
",date(x,true).y,date(x,true).x,y);
return;
}
}
}
}
int q;
int main(){
scanf("%d",&q);
while(q--){
long long x;//#10数据范围为n<=365*10^9
scanf("%lld",&x);
g(x);//处理x
}
return 0;
}
S-T2 zoo
//T2
#include<cstdio>
using namespace std;
typedef unsigned long long ull;
int n,m,c,k;
bool in_zoo[65],in_list[65];
int main(){
scanf("%d%d%d%d",&n,&m,&c,&k);
ull animals=0;// 动 物 家 族
for(int i=1;i<=n;++i){
ull x;
scanf("%llu",&x);
animals|=x;//按位或运算
}
for(int i=0;i<=k-1;++i)
in_zoo[i]=animals&1,animals>>=1;//记录是否有动物第i位为1
for(int i=1;i<=m;i++){
int x;
ull y;
scanf("%d%llu",&x,&y);
in_list[x]=true;//记录是否有饲料第i位为1
}
int cnt=0;
for(int i=0;i<=k-1;++i){
if(in_zoo[i])//如果第i位为1的动物在动物园里,则无论是否需要私聊都可以养
cnt++;
else if(!in_list[i])//如果没有第i位为1的动物在动物园里,但第i位为1的动物不需要饲料也可以养
cnt++;
}
ull ans=((ull)(1)<<(ull)(cnt));//直接输出会爆精度
if(cnt==64 && n==0)//爆ull
printf("18446744073709551616");
else if(cnt==0)//ull的0不会输出(Too short on line 1)(?)
printf("0");
else
printf("%llu",(ans-n));
return 0;
}