第一周比赛题解
第一场比赛就不写题解了,代码都贴了,主要是用来测试oj的
第二场比赛:
第一题代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
cout << " ********" << endl << " ************" << endl << " ####....#." << endl << " #..###.....##...." << endl << " ###.......###### ### ###" << endl << " ........... #...# #...#" << endl << " ##*####### #.#.# #.#.#" << endl << " ####*******###### #.#.# #.#.#" << endl << " ...#***.****.*###.... #...# #...#" << endl << " ....**********##..... ### ###" << endl << " ....**** *****...." << endl << " #### ####" << endl << " ###### ######" << endl << "##############################################################" << endl << "#...#......#.##...#......#.##...#......#.##------------------#" << endl << "###########################################------------------#" << endl << "#..#....#....##..#....#....##..#....#....#####################" << endl << "########################################## #----------#" << endl << "#.....#......##.....#......##.....#......# #----------#" << endl << "########################################## #----------#" << endl << "#.#..#....#..##.#..#....#..##.#..#....#..# #----------#" << endl << "########################################## ############";
return 0;
}
第二题代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=1100000;
const int MAXM=105;
const int MOD=90;
int stone[MAXM];
int a[MAXN];
int f[MAXN];
int L,s,t;
int n;
void init()
{
scanf("%d%d%d%d",&L,&s,&t,&n);
for(int i=1;i<=n;i++)
scanf("%d",&stone[i]);
}
void solve()
{
int tot=0;
for(int i=1;i<=n;i++)
if(stone[i]%s==0)
tot++;
cout<<tot<<endl;
exit(0);
}
void work()//处理石头~缩掉里面的空地
{
sort(stone+1,stone+n+1);
for(int i=1;i<=n;i++)
{
int dist=stone[i]-stone[i-1];
stone[i]=stone[i-1]+dist%MOD;
}
L=(L-stone[n])%MOD+stone[n];
for(int i=1;i<=n;i++)
a[stone[i]]=1;
}
void DP()
{
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=s;i<=L+t;i++)//第一次至少也会跳到s
for(int j=s;j<=t;j++)
if(i>=j)
f[i]=min(f[i],f[i-j]+a[i]);
int ans=(1<<30)-1;
for(int i=L;i<=L+t;i++)
ans=min(ans,f[i]);
cout<<ans<<endl;
}
int main()
{
init();
if(s==t)//特判s==t
solve();
work();
DP();
}
第三题代码:
#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <regex>
#include <map>
#include <cctype>
#include <cmath>
using namespace std;
map<string,int> prio{
{"+",1},
{"-",1},
{"*",2},
{"/",2},
{"^",3},
{"(",4},
};
typedef long long ll;
ll qpow(ll a,ll b){
ll ret=1;
for(ll s=a;b;b>>=1u,s*=s) if(b&1u) ret*=s;
return ret;
}
#define sigop(op) {#op,[](ll a,ll b){return a op b;}}
map<string,function<ll (ll,ll)>> opr{
sigop(+),
sigop(-),
sigop(*),
sigop(/),
{"^",qpow}
};
#undef sigop
ll eval (string const& exp,ll x);
int main() {
string s0;
int n;
getline(cin,s0);
cin>>n;
cin.get();
for (int i=0;i<n;++i){
string s;
getline(cin,s);
bool flag=true;
for(ll a=0;a<=10 && flag;++a)
flag = eval(s,a) == eval(s0,a);
if(flag) cout<<char('A'+i);
}
return 0;
}
template<typename T>
T operator-- (stack<T>& s,int){
T ret=s.top();
s.pop();
return ret;
}
ll eval (string const& e,ll x) {
stack<ll> ons;
stack<string> ops;
stringstream exp(regex_replace(regex_replace(e, regex(" "), ""), regex("([+/*()^-])"), " $1 "));
ll a;
for (string s; exp >> s;)
if (s == "a") ons.push(x);
else if (stringstream(s) >> a) ons.push(a);
else if (s == ")")
for (string op; (op = ops--) != "(";)
ons.push(opr[op](ons--, ons--));
else {
while (!ops.empty() && ops.top() != "(" && prio[s] <= prio[ops.top()])
ons.push(opr[ops--](ons--, ons--));
ops.push(s);
}
while (ons.size() != 1) ons.push(opr[ops--](ons--, ons--));
return ons.top();
}
第四题:
#include<iostream>
#define py printf("YES\n")
#define pn printf("NO\n")
using namespace std;
int a,b,c,n,stop=0;
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d",&a,&b,&c);
if((b==9&&c==30)||(b==1&&c==30)||((b+c)%2==0))py;
else pn;
}
return 0;
}
第五题代码:
#include<iostream>
#include<string>
using namespace std;
string s;
int a[300][305]={0};
int flag=1;
int kk=0;
//x[0~(n-m)]=s[n~m]
int getNum(int x[],int m,int n){
for(int i=n;i>=m;--i)
x[n-i]=s[i]-'0';
}
void print(int x[]){
int i;
for(i=300;i>=0;i--)
if(x[i]!=0) break;
while(i>=0) cout<<x[i--];
cout<<endl;
}
//打印补齐后的第一个数
void print(int l){
for(int i=1;i<=l;++i)
cout<<s[i];
cout<<endl;
}
//x=x+t
void add(int x[],int t){
x[0]+=t;
int i=0;
while(x[i]>=10)
{
x[i+1]+=x[i]/10;
x[i]%=10;
i++;
}
}
//x=x-t
void sub(int x[],int t){
x[0]-=t;
int i=0;
while(x[i]<0)
{
x[i]+=10;
x[i-1]-=1;
i++;
}
}
//前后数位数都足够
bool check(int i,int j,int m,int n){
if(s[i]=='0'||s[m]=='0') return false;
int x[305]={0},y[305]={0};
getNum(x,i,j);
getNum(y,m,n);
add(x,1);
for(int d=0;d<=300;d++)
if(x[d]!=y[d]) return false;
return true;
}
//后一个数位数不够,只判断后一个数与前一个数对应的位数是否相等
bool tailCheck(int i,int j,int m,int n){
if(s[i]=='0'||s[m]=='0') return false;
int x[305]={0},y[305]={0};
getNum(x,i,j);
getNum(y,m,n);
add(x,1);
int d1=300,d2=300;
while(x[d1]==0) d1--;
while(y[d2]==0) d2--;
while(d1>=0&&d2>=0)
{
if(x[d1]!=y[d2]) return false;
d1--;d2--;
}
return true;
}
//判断第一个数的位数是否能为l
bool find(int l){
int i,j,m,n;
i=1;j=l;m=j+1;n=j+l;
if(j==s.size()-1&&s[i]=='0') return false;
while(true)
{
if(j>=s.size()-1) return true;
if(n>=s.size()-1) {n=s.size()-1;if(!tailCheck(i,j,m,n)) return false;}
else if(!check(i,j,m,n)) //前一个数和后一个数的位数都为l
{
if(!check(i,j,m,n+1)) //前一个数位数为l,后一个数位数为l+1
return false;
else {l+=1;n+=1;}
}
i=m;
j=n;
m=j+1;
n=j+l;
}
return true;
}
void Multiply(int x[],int y){
for(int i=0;i<=300;++i)
x[i]*=y;
for(int i=0;i<=300;++i)
if(x[i]>9)
{
x[i+1]+=x[i]/10;
x[i]%=10;
}
}
void add(int x[],int y[]){
for(int i=0;i<=300;++i)
x[i]+=y[i];
int i=0;
while(x[i]>=10)
{
x[i+1]+=x[i]/10;
x[i]%=10;
i++;
}
}
bool comp(int x[],int y[]){
for(int i=300;i>=0;--i)
if(x[i]<y[i]) return true;
else if(x[i]>y[i]) return false;
return false;
}
void getAns(int finalAns[],int l,int k){
int x[305]={0},ans[305]={0};
getNum(x,1,l);
x[l-1]-=1;
Multiply(x,l);
for(int i=0;i<=300;++i)
ans[i]=a[l-1][i]+x[i];
ans[0]+=1+k+kk;
for(int i=0;i<=300;++i)
if(ans[i]>9)
{
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
if(flag==1||comp(ans,finalAns))
for(int i=0;i<=300;++i)
finalAns[i]=ans[i];
}
//判断数组是否为1000....0000的形式
bool Equal1000(int x[]){
int tot=0;
for(int i=0;i<=300;++i)
if(x[i]!=0) tot++;
if(tot>1) return false;
return true;
}
//判断字符串是否为全0
bool Equal000(string s1){
for(int i=0;i<s1.size();++i)
if(s1[i]!='0') return false;
return true;
}
int main()
{
//a[i]表示所有位数<=i的字符串长度和
for(int i=1;i<=200;++i)
{
a[i][i-1]=9;
Multiply(a[i],i);
add(a[i],a[i-1]);
}
int finalAns[305]={0};
flag=1;
string s1;
cin>>s1;
//如果字符串=000...0,则在最前面加上0,令kk=1,最后的答案要减去kk
if(Equal000(s1))
{s1="1"+s1;kk=1;}
//l为字符串中第一个数的位数
//k表示字符串中第一个字符是第一个数的第K+1位,k<l
for(int l=1;l<=s1.size();++l)
for(int k=0;k<l;++k)
{
s=" "+s1;string s2="";
if(k==0)
{
if(find(l))
{getAns(finalAns,l,k);flag=0;}
}
//如果K!=0,则补齐第一个数的前k位
if(k!=0)
{
int x[305]={0};
getNum(x,l-k+1,l-k+k);
//1.直接把第l-k+1至l-k+k之间的数补齐第一个数的前k位
s2="";
int i=k-1;
while(i>=0) s2+=x[i--]+'0';
s=" "+s2+s1;
if(find(l))
{getAns(finalAns,l,k);flag=0;}
//2.如果第l-k+1至l-k+k之间数的形式是10....000,也可以用99....999补齐第一个数的前k位
if(Equal1000(x))
{
s2="";
i=k-1;
while(i>=0) {s2+='9';i--;}
s=" "+s2+s1;
if(find(l))
{getAns(finalAns,l,k);flag=0;}
}
//3.用第l-k+1至l-k+k之间的数减去1,补齐第一个数的前k位
sub(x,1);
i=k-1;
s2="";
while(i>=0) s2+=x[i--]+'0';
s=" "+s2+s1;
if(find(l))
{getAns(finalAns,l,k);flag=0;}
}
}
print(finalAns);
// system("pause");
}
第六题代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1005;
int a[maxn][maxn];
int f[maxn][maxn];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>a[i][j];
f[1][1]=a[1][1];//终点处就直接是该点时间
for(int i=2;i<=n;i++)//一层一层往上推
{
for(int j=2;j<i;j++)//先求出从上一层推出来的最小值
f[i][j]=min(f[i-1][j],f[i-1][j-1])+a[i][j];
f[i][1]=min(f[i-1][1],f[i-1][i-1])+a[i][1];//特殊边界点处理
f[i][i]=min(f[i-1][i-1],f[i-1][1])+a[i][i];//特殊边界点处理
//同一层更新最优解
for(int k=i-1;k>0;k--)//从右往左推 从右往左走的情况更新
f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
for(int l=2;l<=i;l++)//从左往右推 从左往右走的情况更新
f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
/*for(int k=i-1;k>0;k--)//再推一遍从右往左推 从右往左走的情况更新
f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
for(int l=2;l<=i;l++)//再推一遍从左往右推 从左往右走的情况更新
f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
f[i][1]=min(f[i][1],f[i][i]+a[i][1]);*/
}
cout<<f[n][1]<<endl;
}