meeting
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
A new city has just been built. There're nnn interesting places numbered by positive numbers from 111 to nnn. In order to save resources, only exactly n−1n-1n−1 roads are built to connect these nnn interesting places. Each road connects two places and it takes 1 second to travel between the endpoints of any road. There is one person in each of the places numbered x1,x2…xkx_1,x_2 \ldots x_kx1,x2…xk and they've decided to meet at one place to have a meal. They wonder what's the minimal time needed for them to meet in such a place. (The time required is the maximum time for each person to get to that place.)
输入描述:
First line two positive integers, n,kn,kn,k - the number of places and persons.For each the following n−1n-1n−1 lines, there're two integers a,ba,ba,b that stand for a road connecting place aaa and bbb. It's guaranteed that these roads connected all nnn places.On the following line there're kkk different positive integers x1,x2…xkx_1,x_2 \ldots x_kx1,x2…xk separated by spaces. These are the numbers of places the persons are at.
输出描述:
A non-negative integer - the minimal time for persons to meet together.
示例1
输入
4 2 1 2 3 1 3 4 2 4
输出
2
说明
They can meet at place 1 or 3.
备注:
1≤n≤1051 \leq n \leq 10^51≤n≤105
找树的直径d，d/2上取整即为答案
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,rk) for(int i=(a);i<=(rk);++i)
#define dep(i,a,rk) for(int i=(a);i>=(rk);--i)
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
typedef long long ll;
const int maxn=(int)2e5+100;
const ll INF=(ll)1e18;
int n,k,cnt;
map<ll,int> rk;
ll a[maxn],pre[maxn],ls[maxn],mx[maxn<<2];
void PushUp(int rt){mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);}
void build(int l,int r,int rt){
if (l==r){mx[rt]=-INF;return;}
delf; build(lson); build(rson);
PushUp(rt);
}
void update(int pos,ll val,int l,int r,int rt){
if (l==r){mx[rt]=max(mx[rt],val); return;}
delf;
if (pos<=m) update(pos,val,l,m,rt<<1);
else update(pos,val,m+1,r,rt<<1|1);
PushUp(rt);
}
ll query(int L,int R,int l,int r,int rt){
if (L<=l&&r<=R) return mx[rt];
delf;
ll ANS=0;
if (L<=m) ANS=max(ANS,query(L,R,l,m,rt<<1));
if (R>m) ANS=max(ANS,query(L,R,m+1,r,rt<<1|1));
return ANS;
}
bool check(ll x){
build(1,cnt,1);
update(rk[0],0,1,cnt,1);
rep(i,1,n){
int p=lower_bound(ls,ls+cnt,pre[i]-x)-ls+1;
//if(x==0) printf("# pre[i]-x=%d p=%d\n",pre[i]-x,p);
//if(x==0) printf("## pre[i]=%d rk[pre[i]]=%d query(p,cnt,1,cnt,1)=%d\n",pre[i],rk[pre[i]],query(p,cnt,1,cnt,1));
if(p<cnt){
int now=query(p,cnt,1,cnt,1);
if (now) update(rk[pre[i]],now+1,1,cnt,1);
else update(rk[pre[i]],a[i]<=k,1,cnt,1);
}
else update(rk[pre[i]],a[i]<=k,1,cnt,1);
}
return query(1,cnt,1,cnt,1)>=k;
}
void solve(){
scanf("%d%d",&n,&k);
rep(i,1,n) scanf("%lld",&a[i]),ls[i]=pre[i]=pre[i-1]+a[i];
ls[0]=0; cnt=0; rk.clear();
sort(ls,ls+1+n);
rep(i,0,n) if(!rk.count(ls[i])) rk[ls[i]]=++cnt;
unique(ls,ls+1+n);
ll l=-(ll)1e18,r=(ll)1e18,mid,ans=(ll)1e18;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=min(ans,mid);
else l=mid+1;
}
printf("%lld\n",ans);
}
int main(){
int QAQ;cin>>QAQ;
while(QAQ--) solve();
return 0-0;
}
xor
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
Your are given n sets.Every set contains some integers.
We say a set can express an integer, only when there exists a subset of the set such that the bitwise-xor of the elements in the subset is equal to that integer.
Now you need to answer m queries. Each query will give you three integers l,r,x and you should answer if for every i∈[l,r]i \in [l,r]i∈[l,r] ,the i-th set can express x.
输入描述:
The first line contains two integers n,m.
For each of the following n lines, the first integer sz stands for the size of this set and the following sz integers stand for the elements in this set. The sets are described from number 1 to n.
For each of the following m lines, there're three integers l,r,x that means a query.
输出描述:
For each query, output a line.
If for every i∈[l,r]i \in [l,r]i∈[l,r] ,the i-th set can express x, you need to print “YES”, and "NO" otherwise.
示例1
输入
1 3 2 1 2 1 1 0 1 1 3 1 1 4
输出
YES YES NO
备注:
1≤n,m≤500001 \le n,m \le 500001≤n,m≤50000 ，1≤sz≤321 \le sz \le 321≤sz≤32，1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n ，the every integer in input ∈[0,232)\in [0,2^{32})∈[0,232)。
数论队友写
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
struct LinearBase
{
int sz;
uint W[33], C[33];
LinearBase() : sz(0) {}
uint Residual(uint x, uint *c = NULL) const
{
for (int i = 0; i < sz; i ++)
if ((x ^ W[i]) < x)
{
x ^= W[i];
if (c != NULL)
*c ^= C[i];
}
return x;
}
uint Get(uint state) const
{
uint res = 0;
for (int i = 0; i < sz; i ++)
if ((state >> i) & 1)
res ^= W[i];
return res;
}
bool operator == (const LinearBase &obj) const
{
if (sz != obj.sz)
return false;
for (int i = 0; i < sz; i ++)
if (W[i] != obj.W[i])
return false;
return true;
}
void Add(uint x, uint c = 0)
{
x = Residual(x, &c);
if (!x) return ;
W[sz] = x, C[sz] = c, sz ++;
for (int i = sz - 1; i; i --)
{
if (W[i] > W[i - 1])
swap(W[i], W[i - 1]), swap(C[i], C[i - 1]);
else
{
for (int j = i - 1; j >= 0; j --)
if ((W[j] ^ W[i]) < W[j])
W[j] ^= W[i], C[j] ^= C[i];
break ;
}
}
}
static LinearBase Merge(const LinearBase &lhs, const LinearBase &rhs)
{
if (lhs.sz == 32)
return rhs;
else if (rhs.sz == 32)
return lhs;
else if (lhs == rhs)
return lhs;
LinearBase tmp, res;
for (int i = 0; i < lhs.sz; i ++)
{
uint t = rhs.Residual(lhs.W[i]), c = 1u << i;
uint r = tmp.Residual(t, &c);
if (r == 0)
res.Add(lhs.Get(c));
else tmp.Add(r, c);
}
return res;
}
}a[50100];
struct q{
int l;
uint x;int id;
};
vector<q> v[50100];
int fa[50100];
int ans[50100];
int gao(int pos){
if(fa[pos]==pos) return pos;
int res=gao(fa[pos]);
a[pos]=LinearBase::Merge(a[pos],a[fa[pos]]);
fa[pos]=res;
return res;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++){
int k;
cin>>k;
for(int j=1;j<=k;j++){
uint tmp;
scanf("%u",&tmp);
a[i].Add(tmp);
}
}
for(int i=1;i<=m;i++){
int l,r;
uint x;
scanf("%d%d%u",&l,&r,&x);
v[r].push_back((q){l,x,i});
}
for(int i=1;i<=n;i++){
int len=(int)v[i].size();
for(int j=0;j<len;j++){
q& x=v[i][j];
gao(x.l);
ans[x.id]=(a[x.l].Residual(x.x)==0);
}
if(i<n) fa[i]=i+1;
}
for(int i=1;i<=m;i++){
if(ans[i]){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return 0;
}
sequence
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
Your are given two sequences a1…na_{1 \dots n}a1…n and b1…nb_{1 \dots n}b1…n .You need to answer max1≤l≤r≤n{min(al…r)×sum(bl…r)}\displaystyle \max_{1 \le l \le r \le n} \{min(a_{l \dots r}) \times sum(b_{l \dots r})\}1≤l≤r≤nmax{min(al…r)×sum(bl…r)} 。
Where min(a) means the minimal value of every element of sequence a, sum(a) means the sum of every element of sequence a .
输入描述:
The first line contains an integer n .
The second line contains n integers meaning a1…na_{1 \dots n}a1…n .
The third line contains n integers meaning b1…nb_{1 \dots n}b1…n .
输出描述:
An integer meaning the answer.
示例1
输入
3 1 -1 1 1 2 3
输出
3
备注:
For all test datas, 1≤n≤3×106,−106≤ai,bi≤1061 \leq n \leq 3 \times 10^6,-10^6 \leq a_i,b_i \leq 10^61≤n≤3×106,−106≤ai,bi≤106.
乱搞题，随便过
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e6+100;
ll n,a[maxn],b[maxn];
void solve(){
rep(i,1,n) scanf("%lld",&a[i]);
rep(i,1,n) scanf("%lld",&b[i]);
ll mina=a[1],sum=b[1],ans=mina*sum;
rep(i,2,n){
//ans=max(ans,a[i]*b[i]);
if(sum>=0) sum+=b[i],mina=min(mina,a[i]);
else sum=b[i],mina=a[i];
ans=max(ans,sum*mina);
a[i]*=-1;b[i]*=-1;
}
mina=a[1],sum=b[1],ans=max(ans,mina*sum);
rep(i,2,n){
//ans=max(ans,a[i]*b[i]);
if(sum>=0) sum+=b[i],mina=max(mina,a[i]);
else sum=b[i],mina=a[i];
ans=max(ans,sum*mina);
}
printf("%lld\n",ans);
}
int main(){
while(~scanf("%lld",&n)) solve();
}
triples I
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
Doctor Elephant is testing his new program: output the bitwise or of the numbers inputed. He has decided to input several multiples of 3 and the output of the program should be his favorite number aaa. Because he is lazy, he decided to input as few numbers as possible. He wants you to construct such an input for every aaa he chose. It's guaranteed that for every aaa in the input there is such a solution. If there're multiple solutions you can output any.
输入描述:
There're multiple test cases in a test file.The first line contains a positive integer TTT - the number of test cases.In each of the following TTT lines there is one positive integer aaa.
输出描述:
For each test case output a line. First you need to output the number of numbers in your input, and then you need to output these numbers, separating by spaces.
示例1
输入
2 3 7
输出
1 3 2 3 6
说明
3=3, (3|6)=7
备注:
1≤T≤1051 \leq T \leq 10^51≤T≤105, 1≤a≤10181 \leq a \leq 10^{18}1≤a≤1018.
一个二进制位mod 3只可能是1或者2。
如果a是3的倍数，那么我们直接取{a}即可。
否则如果a的二进制位只有一位或两位，我们根本取不出0以外的三的倍数，所以无解。
接下来考虑a至少有三位的情况。
若a mod 3=1：
如果a中的二进制位有至少两个mod 3=1的，设它们为p和q，我们取{a-p,a-q}即可。
如果a中的二进制位有恰好一个mod 3=1的，那么设mod 3=1的这个位为p，mod 3=2的某个位为q，我们取{a-p,+q}即可。
如果a中的二进制位没有mod 3=1的，那么假设有三个mod 3=2的位p,qr，我们取{a- p-q,p+qr}即可。如果a中的二进制位
p-q,p+qr}即可。
若a mod 3=2只需把上面的讨论中1与2互换即可，是完全对称的。
#include<iostream>
#include<cstdio>
using namespace std;
long long cas,z,x,n,m,w,h,a[100],b[400],p,k,t;
int main()
{
b[1]=1;
for (int i=2;i<=63;i++)
b[i]=b[i-1]*2;
scanf("%lld",&cas);
while (cas--)
{
scanf("%lld",&z);
x=z;n=0;w=0;h=0;
while (x)
{
a[++n]=x%2;
x=x/2;
if (a[n])
{
if (n%2) w++;
else h++;
}
}
if (z%3==0) printf("1 %lld\n",z);
else
{
//if (z%3==1)
{
p=1;
if (p&&(h==0||w==0))
{
k=0;
for (int i=1;i<=n;i++)
if (a[i])
{
if (z%3) {z=z-b[i];k+=b[i];}
else if (k%3) k+=b[i];
}
printf("2 %lld %lld\n",z,k);
//printf("%lld\n",z|k);
p=0;
}
if (p)
{
k=0;
for (int i=1;i<=n;i++)
if (a[i])
{
if ((z-b[i])%3==0)
{
z-=b[i];k+=b[i];
}
if ((z%3==0)&&((k+b[i])%3==0)||(z%3)&&((k+z+b[i])%3==0)) k+=b[i];
}
printf("2 %lld %lld\n",z,k);
//printf("%lld\n",z|k);
}
}
}
}
return 0;
}
triples II
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Doctor Elephant is testing his new program: output the bitwise or of the numbers inputed. He has decided to input nnn multiples of 3 and the output of the program should be his favorite number aaa. He wants to know how many possible sequences are there. Because the answer can be large, you only need to output the answer modulo 998244353998244353998244353.
输入描述:
There're multiple test cases in a test file.The first line contains a positive integer TTT - the number of test cases.In each of the following TTT lines there're two non-negative integers nnn and aaa.
输出描述:
For each test case output a line - the number of such sequences modulo 998244353998244353998244353.
示例1
输入
3 3 3 2 7 233 333
输出
7 2 650745136
备注:
1≤T≤5001 \leq T \leq 5001≤T≤500，1≤n≤10181 \leq n \leq 10^{18}1≤n≤1018，0≤a≤10180 \leq a \leq 10^{18}0≤a≤1018。
如果a中为1的二进制位在b中也都为1，我们称a是b的'子集'。
考虑如果只要求最后的答案是a的'子集'，那么我们只需要保证每次选的数都是a的'子集'即可。
考虑计数是a的'子集'并且是3的倍数的数，我们只需要简单地进行dp，记f[i]j为考虑a的前i位的'子集'并且当前mod 3的值为j的数的个数即可。
回到原问题，我们只需要枚举最后实际或出来的数是a的哪一'子集'，进行容斥即可。
直接枚举a的'子集'复杂度难以接受，但是我们注意到每一个子集的贡献只和这一'子集'中mod 3=1和2的二进制位分别有多少个有关。我们枚举分别有多少个，组合数算出这一种'子集'有多少个，再进行dp即可。
不需要真的枚举一个子集进行dp，而是预处理每种'子集'的答案，每组数据只需重新求n次方。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll md=998244353;
ll dp[70][70][3];
ll c[70][70];
ll qp(ll a, ll b){
ll ret=1;
while(b){
if(b&1) ret=ret*a%md;
a=a*a%md;
b>>=1;
}
return ret;
}
int main(){
for(int i=0;i<=64;i++){
for(int j=0;j<=64;j++){
if(i==0 && j==0) dp[i][j][0]=1;
else if(i!=0){
for(int k=0;k<=2;k++) dp[i][j][k]=(dp[i-1][j][k]+dp[i-1][j][(k+2)%3])%md;
}
else{
for(int k=0;k<=2;k++) dp[i][j][k]=(dp[i][j-1][k]+dp[i][j-1][(k+1)%3])%md;
}
}
}
c[0][0]=1;
for(int i=1;i<=64;i++){
c[i][0]=1;
c[i][i]=1;
for(int j=1;j<i;j++){
c[i][j]=(c[i-1][j]+c[i-1][j-1])%md;
}
}
int T;
scanf("%d",&T);
while(T--){
ll n,a;
scanf("%lld%lld",&n,&a);
int u[2];
u[0]=0,u[1]=0;
int pt=0;
while(a){
if(a&1) u[pt]++;
pt^=1;
a>>=1;
}
ll ans=0;
for(int i=0;i<=u[0];i++){
for(int j=0;j<=u[1];j++){
ll tmp=(c[u[0]][i]*c[u[1]][j]%md*qp(dp[u[0]-i][u[1]-j][0],n)%md);
if((i+j)%2==0){
ans=(ans+tmp)%md;
}
else{
ans=(ans-tmp+md)%md;
}
}
}
printf("%lld\n",ans);
}
return 0;
}
string
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
We call a,ba,ba,b non-equivalent if and only if a≠ba \neq ba=b and a≠rev(b)a \neq rev(b)a=rev(b), where rev(s)rev(s)rev(s) refers to the string obtained by reversing characters of sss, for example rev(abca)=acbarev(abca)=acbarev(abca)=acba.
There is a string sss consisted of lower-case letters. You need to find some substrings of sss so that any two of them are non-equivalent. Find out what's the largest number of substrings you can choose.
输入描述:
A line containing a string sss of lower-case letters.
输出描述:
A positive integer - the largest possible number of substrings of sss that are non-equivalent.
示例1
输入
abac
输出
8
说明
The set of following substrings is such a choice: abac,b,a,ab,aba,bac,ac,cabac,b,a,ab,aba,bac,ac,cabac,b,a,ab,aba,bac,ac,c.
备注:
1≤∣s∣≤2×1051 \leq |s|\leq 2 \times 10^51≤∣s∣≤2×105, sss is consisted of lower-case letters.
考虑rev(s)和s中的不同子串个数，那么这样s和rev(s)就会大约恰好被算两次！
其实并不是所有s都是这样，如果s本身是回文的，那么s=rev(s)。
求出rev(s)和s中的不同子串个数p
求出s中的不同回文串个数q
答案即为(p+q)/2
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn = 1e6+100;
struct SAM{
int next[maxn][27],fa[maxn],len[maxn];
int root,tot,last; ll dp[maxn];
void init(){
tot=0;
memset(dp,-1,sizeof(dp));
last=root=newnode(0);
}
int newnode(int l){
fa[tot]=-1;
for(int i=0;i<27;++i) next[tot][i]=-1;
len[tot++]=l; return tot-1;
}
void insert(int x){
int p=last; int cur=newnode(len[p]+1);
while(p!=-1&&next[p][x]==-1){
next[p][x]=cur; p=fa[p];
}
if(p==-1) fa[cur]=root;
else{
int q=next[p][x];
if(len[q]==len[p]+1) fa[cur]=q;
else{
int tmp=newnode(len[p]+1);
memcpy(next[tmp],next[q],sizeof(next[q]));
fa[tmp]=fa[q]; fa[q]=fa[cur]=tmp;
while(p!=-1&&next[p][x]==q){
next[p][x]=tmp; p=fa[p];
}
}
}
last=cur;
}
ll dfs(int u){
if(dp[u]!=-1) return dp[u];
ll res=1;
for(int i=0;i<26;++i){
if(next[u][i]==-1) continue;
res+=dfs(next[u][i]);
}
return dp[u]=res;
}
}sam;
struct PAM{
int next[maxn][26],fail[maxn],len[maxn];
int txt[maxn];
int tot,root0,root1,last,size;
void init(){
last=tot=size=0; txt[size]=-1;
root0=newnode(0); root1=newnode(-1);
fail[root0]=1; fail[root1]=0;
}
int newnode(int l){
len[tot]=l;
memset(next[tot],0,sizeof(next[tot]));
tot++; return tot-1;
}
int getfail(int x){
while(txt[size-len[x]-1]!=txt[size]) x=fail[x];
return x;
}
void insert(int c){
txt[++size]=c; int now=getfail(last);
if(!next[now][c]){
int tmp=newnode(len[now]+2);
fail[tmp]=next[getfail(fail[now])][c];
next[now][c]=tmp;
}
last=next[now][c];
}
}pam;
char s[maxn];
int n;
void solve(){
scanf("%s",s); n=strlen(s); sam.init(); pam.init();
rep(i,0,n-1) sam.insert(s[i]-'a'),pam.insert(s[i]-'a'); sam.insert(26);
dep(i,n-1,0) sam.insert(s[i]-'a');
printf("%lld\n",(sam.dfs(sam.root)+pam.tot-2-1)/2);
}
int main(){
solve();
}
free
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
Your are given an undirect connected graph.Every edge has a cost to pass.You should choose a path from S to T and you need to pay for all the edges in your path. However, you can choose at most k edges in the graph and change their costs to zero in the beginning. Please answer the minimal total cost you need to pay.
输入描述:
The first line contains five integers n,m,S,T,K.
For each of the following m lines, there are three integers a,b,l, meaning there is an edge that costs l between a and b.
n is the number of nodes and m is the number of edges.
输出描述:
An integer meaning the minimal total cost.
示例1
输入
3 2 1 3 1 1 2 1 2 3 2
输出
1
备注:
1≤n,m≤103,1≤S,T,a,b≤n,0≤k≤m,1≤l≤1061 \le n,m \le 10^3,1 \le S,T,a,b \le n,0 \le k \le m,1 \le l \le 10^61≤n,m≤103,1≤S,T,a,b≤n,0≤k≤m,1≤l≤106.
Multiple edges and self loops are allowed.
记f[i]j表示从起点走到i，至多免费走j条边的花费最小值。
f[i]j=min(f[i]j-1],min(f[x]j-1],f[x]j+e) (x和i有边权为e的边)
从小到大枚举j进行转移。
f[i]j=min(f[i]j-1]
从小到大枚举j进行转移
以min(f[i]j-1],f[x]j-1] (x和i有边)作为i号点距离的初始值
使用dijkstra等算法跑最短路
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
#define pii pair<int,pair<int,int> >
const int maxn=(int)1e3+100;
const int INF=0x3f3f3f3f;
int n,m,s,t,K;
struct Edge{
int u,v,w,next;
}g[maxn<<1];
int head[maxn],cnt=1,dis[maxn][maxn];
void addedge(int u, int v, int w){
g[cnt]={u,v,w,head[u]};head[u]=cnt++;
}
void dijkstra(){
priority_queue<pii,vector<pii>,greater<pii> > Q;
memset(dis,INF,sizeof(dis));
dis[s][0]=0;
Q.push({0,{s,0}});
while(!Q.empty()) {
int x=Q.top().second.first,k=Q.top().second.second;
Q.pop();
for(int i = head[x]; i; i = g[i].next) {
int v=g[i].v,w=g[i].w;
if(dis[x][k]+w<dis[v][k]){
dis[v][k]=dis[x][k]+w;
Q.push({dis[v][k],{v,k}});
}
if(k+1<=K&&dis[x][k]<dis[v][k+1]){
dis[v][k+1]=dis[x][k];
Q.push({dis[v][k+1],{v,k+1}});
}
}
}
}
void solve(){
rep(i,1,m){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
if(u==v) continue;
addedge(u,v,w); addedge(v,u,w);
}
dijkstra();
int ans=INF;
rep(i,0,K) ans=min(ans,dis[t][i]);
printf("%d\n",ans);
}
int main(){
while(~scanf("%d%d%d%d%d",&n,&m,&s,&t,&K)) solve();
}
number
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
300iq loves numbers who are multiple of 300. One day he got a string consisted of numbers. He wants to know how many substrings in the string are multiples of 300 when considered as decimal integers. Note that leading and trailing zeros are allowed (both in original string and substrings you chose) and the same substring appearing in different places can be counted multiple times.
输入描述:
A single line consisting a string consisted of characters '0' to '9'.
输出描述:
The number of substrings that are multiples of 300 when considered as decimal integers.
示例1
输入
600
输出
4
说明
'600', '0', '0', '00' are multiples of 300. (Note that '0' are counted twice because it appeared two times)
示例2
输入
123000321013200987000789
输出
55
备注:
let the string in the input be s, 1≤∣s∣≤1051 \leq |s| \leq 10^51≤∣s∣≤105.
简单DP
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int z,x,n,m,w,h,a[100001][300];
char s[100001];
long long ans;
int main()
{
scanf("%s",s);ans=0;
for (int i=0;i<strlen(s);i++)
{
if (i)
for (int j=0;j<300;j++)
a[i][(j*10+s[i]-'0')%300]+=a[i-1][j];
a[i][s[i]-'0']++;
ans+=a[i][0];
}
printf("%lld",ans);
return 0;
}
