A.小A买彩票
一开始想到排列组合，但是发现太菜不会写orz。看到数据范围小，想直接暴力，TLE，然后，联想到记忆化搜素减少搜索，所以应该是dp。但是菜鸡并不会设计状态（划掉），所以，只能写dfs+记忆化搜索。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a);
a=a*a;
n>>=1;
}
return ans;
}
//==============================================================
int n;
ll f[200][200];
ll dfs(ll k,ll pos){
if(f[k][pos]!=-1) return f[k][pos];
if(k>n){
if(pos>=3*n) return 1;
else return 0;
}
ll res=0;
rep(i,1,4){
res+=dfs(k+1,pos+i);
}
f[k][pos]=res;
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(n);
memset(f,-1,sizeof(f));
ll ans=dfs(1,0);
if(ans==0){
puts("0/1");
return 0;
}
ll fm=ksm(4,n);
ll gg=gcd(fm,ans);
printf("%lld/%lld\n",ans/gg,fm/gg);
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}B.「金」点石成金
以前写过，数据范围小，所以直接搜索就行了。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=20;
ll n,a[maxn],b[maxn],c[maxn],d[maxn];
ll ans=-inf;
void dfs(int idx,ll cai,ll mo){
if(idx>n){
ans=max(ans,cai*mo);
return;
}
rep(i,1,2){
if(i==1){
dfs(idx+1,cai+a[idx],max(0ll,mo-b[idx]));
}
if(i==2){
dfs(idx+1,max(cai-d[idx],0ll),mo+c[idx]);
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(n);
rep(i,1,n){
read(a[i]),read(b[i]),read(c[i]),read(d[i]);
}
dfs(1,0,0);
write(ans);
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}C.小阳的贝壳
感觉是这次最难的题目了。这道题询问有三种：给区间加，求区间差值最大，求区间gcd。如果只有前两个，还是比较好想到维护一个差分数组的。但是对于第三个，我们需要知道结论：
再衍生一下就是:
因此，我们只需要维护差分数组就行了。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define int long long
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//¿´ÊÇ·ñÒªmod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=1e5+10;
#define lson (rt<<1)
#define rson (rt<<1|1)
struct node{
int l,r,m,GCD;
int sum;
}tree[maxn<<2];
int a[maxn];
int n,m;
void pushup(int rt){
tree[rt].m=max(tree[lson].m,tree[rson].m);
tree[rt].GCD=gcd(tree[lson].GCD,tree[rson].GCD);
tree[rt].sum=tree[lson].sum+tree[rson].sum;
}
void build(int l,int r,int rt){
tree[rt].l=l,tree[rt].r=r;
if(l==r){
tree[rt].m=tree[rt].GCD=abs(a[l]);
tree[rt].sum=a[l];
return;
}
int m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt);
}
void modify(int tar,int val,int rt){
int l=tree[rt].l,r=tree[rt].r;
if(l==r){
a[l]+=val;
tree[rt].m=tree[rt].GCD=abs(a[l]);
tree[rt].sum=a[l];
return ;
}
int m=(l+r)>>1;
if(tar<=m) modify(tar,val,lson);
else modify(tar,val,rson);
pushup(rt);
}
int qm(int ql,int qr,int rt){
int l=tree[rt].l,r=tree[rt].r;
if(ql<=l&&r<=qr){
return tree[rt].m;
}
int m=(l+r)>>1;
int res=0;
if(ql<=m) res=max(res,qm(ql,qr,lson));
if(qr>m) res=max(res,qm(ql,qr,rson));
return res;
}
int qgcd(int ql,int qr,int rt){
int l=tree[rt].l,r=tree[rt].r;
if(ql<=l&&qr>=r){
return tree[rt].GCD;
}
int res=0;
int m=(l+r)>>1;
if(ql<=m) res=gcd(res,qgcd(ql,qr,lson));
if(m<qr) res=gcd(res,qgcd(ql,qr,rson));
return res;
}
int qsum(int ql,int qr,int rt){
int l=tree[rt].l,r=tree[rt].r;
if(ql<=l&&r<=qr){
return tree[rt].sum;
}
int m=(l+r)>>1;
int res=0;
if(ql<=m) res+=qsum(ql,qr,lson);
if(qr>m) res+=qsum(ql,qr,rson);
return res;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(n),read(m);
rep(i,1,n) read(a[i]);
per(i,1,n) a[i]-=a[i-1];
build(1,n,1);
while(m--){
int opt;
read(opt);
if(opt==1){
int l,r,x;
read(l),read(r),read(x);
modify(l,x,1);
if(r<n) modify(r+1,-x,1);
}
else if(opt==2){
int l,r;
read(l),read(r);
if(l==r){
cout<<0<<endl;
continue;
}
write(qm(l+1,r,1));
putchar('\n');
}
else if(opt==3){
int l,r;
read(l),read(r);
int t=qsum(1,l,1);
if(l==r){
write(t);
}
else{
write(gcd(qgcd(l+1,r,1),t));
}
putchar('\n');
}
}
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}D.Forsaken喜欢字符串
纯暴力题，暴力统计每个字符串的每个子串的出现次数，后暴力求和就行了，具体看代码：
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//¿´ÊÇ·ñÒªmod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=5e4+10;
int n,k,q;
string str[maxn];
map<string,int> ans;
void deal(){
rep(i,1,n){
rep(l,1,k){
rep(j,0,k-l){
ans[str[i].substr(j,l)]++;
}
}
}
}
int solve(int x,int len){
int res=0;
rep(j,0,k-len){
int cnt=0;
string sub=str[x].substr(j,len);
rep(i,0,k-len){
if(str[x].substr(i,len)==sub){
cnt++;
}
}
res+=(ans[sub]-cnt)*sub.length();
}
return res;
}
int main()
{
IOS;
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
cin>>n>>k;
rep(i,1,n){
cin>>str[i];
}
cin>>q;
deal();
while(q--){
int x,len;
cin>>x>>len;
cout<<solve(x,len)<<endl;
}
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}E.Board
思维题。因为每一次加都是针对一整行或一整列的，所以，我们挑选形成对角线的一组（像二阶行列式求值的时候的，斜的那n个数），刚好都处于不同行，不同列，加起来就是修改过程中所有加数的和sum1了。
同理，-1所在的那条对角线也应该是这个和，这时候，我们就可以利用刚才求出的sum1，以及-1所在对角线的，其他数的和sum2，做个差值，求出来的，就是-1处缺少的这个数。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxn=1e3+10;
int a[maxn][maxn];
int hang[maxn],lie[maxn];
int n;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t c1 = clock();
//===========================================================
read(n);
memset(hang,inf,sizeof(hang));
memset(lie,inf,sizeof(lie));
int h,l;
rep(i,1,n){
rep(j,1,n){
read(a[i][j]);
if(a[i][j]==-1){
h=i,l=j;
}
}
}
int p1=h+1,p2=l;
int cnt=0;
int s=0;
while(cnt<n){
cnt++;
s+=a[p1][p2];
p1++,p2++;
if(p1>n) p1%=n;
if(p2>n) p2%=n;
}
int pp1=h,pp2=l;
int cntt=0;
int ss=0;
while(cntt<n){
cntt++;
if(a[pp1][pp2]!=-1){
ss+=a[pp1][pp2];
}
pp1++,pp2++;
if(pp1>n) pp1%=n;
if(pp2>n) pp2%=n;
}
write(s-ss);
//===========================================================
std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}
京公网安备 11010502036488号