题目描述
在幻想乡，东风谷早苗是以高达控闻名的高中生宅巫女。某一天，早苗终于入手了最新款的钢达姆模型。作为最新的钢达姆，当然有了与以往不同的功能了，那就是它能够自动行走，厉害吧（好吧，我自重）。早苗的新模型可以按照输入的命令进行移动，命令包含’E’、’S’、’W’、’N’四种，分别对应四个不同的方向，依次为东、南、西、北。执行某个命令时，它会向着对应方向移动一个单位。作为新型机器人，自然不会只单单执行一个命令，它可以执行命令串。对于输入的命令串，每一秒它会按照命令行动一次。而执行完命令串最后一个命令后，会自动从头开始循环。在0时刻时早苗将钢达姆放置在了(0,0)的位置，并且输入了命令串。她想要知道T秒后钢达姆所在的位置坐标。
向东移动，坐标改变改变为(X+1,Y);
向南移动，坐标改变改变为(X,Y-1);
向西移动，坐标改变改变为(X-1,Y);
向北移动，坐标改变改变为(X,Y+1);
输入输出格式
输入格式：
第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令
第2行：一个正整数T
输出格式：
第1行：两个整数，表示T秒时，钢达姆的坐标
输入输出样例
NSWWNSNEEWN
12
-1 3
说明
对于60%的数据：T <= 500,000且命令串长度 <= 5,000
对于100%的数据：T <= 2,000,000,000且命令串长度<= 5,000
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 10010
using namespace std;
int n,x,y;
char s[maxn];
int main()
{
freopen("robot.in","r",stdin);
freopen("robot.out","w",stdout);
scanf("%s%d",s,&n);
int len=strlen(s);
for(int i=;i<len;i++){
if(s[i]=='E')x++;
if(s[i]=='S')y--;
if(s[i]=='W')x--;
if(s[i]=='N')y++;
}
int c=n/len;
x*=c;y*=c;
c=n%len;
for(int i=;i<c;i++){
if(s[i]=='E')x++;
if(s[i]=='S')y--;
if(s[i]=='W')x--;
if(s[i]=='N')y++;
}
printf("%d %d\n",x,y);
return ;
}
题目描述
在幻想乡，西行寺幽幽子是以贪吃闻名的亡灵。不过幽幽子可不是只会吃，至少她还管理着亡灵界。话说在幽幽子居住的白玉楼有一颗常年不开花的樱树——西行妖。幽幽子决定去收集人间的春度，聚集起来让西行妖开花。很快，作为幽幽子家园艺师的魂魄妖梦收集到了M个单位的春度。并且在这段时间里，幽幽子计算出要让西行妖开出一朵花需要N个单位的春度。现在幽幽子想要知道，使用所有的春度，能够让西行妖开出多少朵花。
输入输出格式
输入格式：
输入格式 第1行：一个正整数M
第2行：一个正整数N
N,M的位数不超过L，L的范围在题目后面给出
输出格式：
1行：一个整数ans，表示能开出花的朵数
输入输出样例
73861758
12471
5922
说明
对于60%的数据：L <= 2,000且ans <= 2,000
对于100%的数据：L <= 20,000且ans <= 2,000,000,000
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 21010
#define ll long long
using namespace std;
ll l,r,ans,a[maxn],b[maxn];
char s1[maxn],s2[maxn];
bool Judge(ll x){
ll c[maxn];memset(c,,sizeof(c));
c[]=b[];
for(int i=;i<=c[];i++)
c[i]=b[i]*x;
for(int i=;i<=c[];i++)
if(c[i]>){
c[i+]+=c[i]/;
c[i]%=;
}
while(c[c[]+]){
c[]++;
c[c[]+]+=c[c[]]/;
c[c[]]%=;
}
if(a[]>c[])return ;
if(a[]<c[])return ;
for(int i=c[];i>=;i--){
if(a[i]>c[i])return ;
if(a[i]<c[i])return ;
}
return ;
}
int main()
{
freopen("spring.in","r",stdin);
freopen("spring.out","w",stdout);
scanf("%s%s",s1,s2);
int l1=strlen(s1);
int l2=strlen(s2);
for(int i=;i<=l1;i++)
a[i]=s1[l1-i]-'';
for(int i=;i<=l2;i++)
b[i]=s2[l2-i]-'';
a[]=l1;b[]=l2;
l=;r=;
while(l<=r){
ll mid=(l+r)/;
if(Judge(mid)){
ans=mid;l=mid+;
}
else r=mid-;
}
cout<<ans;
return ;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 20010
using namespace std;
int l1,l2,p,ans[maxn];
char s1[maxn],s2[maxn];
int main()
{
scanf("%s%s",s1,s2);
l1=strlen(s1);l2=strlen(s2);
while(l2<=l1){
while(strncmp(s1,s2,l2)>=){
for(int i=l2-;i>=;i--)
s1[i]=s1[i]-s2[i]+'';
for(int i=l2-;i>=;i--)
if(s1[i]<''){
s1[i-]--;s1[i]+=;
}
ans[p]++;
}
p++;l2++;
for(int i=l2-;i>=;i--)
s2[i]=s2[i-];
s2[]='';
}
int k=;
for(int i=;i<l1;i++)
if(ans[i]){
k=i;break;
}
for(int i=k;i<p;i++)
printf("%d",ans[i]);
return ;
}
题目描述
在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。小河可以看作一列格子依次编号为0到N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子i时，她只会移动到i+L到i+R中的一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。每一个格子都有一个冰冻指数A[i]，编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。开始时，琪露诺在编号0的格子上，只要她下一步的位置编号大于N就算到达对岸。
输入输出格式
输入格式：
第1行：3个正整数N, L, R
第2行：N+1个整数，第i个数表示编号为i-1的格子的冰冻指数A[i-1]
输出格式：
一个整数，表示最大冰冻指数。保证不超过2^31-1
输入输出样例
5 2 3
0 12 3 11 7 -2
11
说明
对于60%的数据：N <= 10,000
对于100%的数据：N <= 200,000
对于所有数据 -1,000 <= A[i] <= 1,000且1 <= L <= R <= N
暴力60:
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 200010
using namespace std;
int n,l,r,v[maxn],f[maxn],ans,c[maxn];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
void Dfs(int k){
if(k<=n)c[++c[]]=k;
if(k==)return;
for(int i=max(k-r,);i<=max(k-l,);i++){
if(f[i]+v[k]==f[k]){
Dfs(i);
break;
}
}
}
int main()
{
freopen("iceroad.in","r",stdin);
freopen("iceroad.out","w",stdout);
n=init();l=init();r=init();
for(int i=;i<=n;i++)
v[i]=init();
for(int i=;i<=n;i++)
for(int j=l;j<=r;j++)
f[i+j]=max(f[i+j],f[i]+v[i+j]);
int k=;
for(int i=n+;i<=n+r;i++)
if(f[i]>ans){
ans=f[i];k=i;
}
printf("%d\n",ans);
Dfs(k);
for(int i=c[];i>=;i--)
printf("%d ",c[i]);
printf("-1\n");
return ;
}
线段树:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 400010
#define lc k*2
#define rc k*2+1
#define mid (l+r)/2
using namespace std;
int n,l,r,v[maxn],f[maxn],ans,mxx[maxn*],c[maxn];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
void Build(int k,int l,int r){
if(l!=r){
Build(lc,l,mid);
Build(rc,mid+,r);
mxx[k]=max(mxx[lc],mxx[rc]);
}
else mxx[k]=;
}
void Change(int k,int l,int r,int x,int y,int z){
if(x<=l&&y>=r){
mxx[k]=z;return;
}
if(x<=mid)Change(lc,l,mid,x,y,z);
if(y>mid)Change(rc,mid+,r,x,y,z);
mxx[k]=max(mxx[lc],mxx[rc]);
}
int Query(int k,int l,int r,int x,int y){
if(x<=l&&y>=r)return mxx[k];
int ret=;
if(x<=mid)ret=max(ret,Query(lc,l,mid,x,y));
if(y>mid)ret=max(ret,Query(rc,mid+,r,x,y));
return ret;
}
void Dfs(int k){
if(k<=n)c[++c[]]=k;
if(k==)return;
for(int i=max(k-r,);i<=max(k-l,);i++){
if(f[i]+v[k]==f[k]){
Dfs(i);
break;
}
}
}
int main()
{
freopen("iceroad9.in","r",stdin);
//freopen("iceroad.out","w",stdout);
n=init();l=init();r=init();
for(int i=;i<=n;i++)
v[i]=init();
Build(,,n+r);
for(int i=l;i<=n+r;i++){
int L=i-r,R=i-l;
L=max(L,);R=max(R,);
int mx=Query(,,n+r,L,R);
f[i]=max(f[i],mx+v[i]);
Change(,,n+r,i,i,f[i]);
}
int k=;
for(int i=n+;i<=n+r;i++)
if(f[i]>ans){
ans=f[i];k=i;
}
printf("%d\n",ans);
Dfs(k);
for(int i=c[];i>=;i--)
printf("%d ",c[i]);
printf("-1\n");
return ;
}
单调队列:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 400010
using namespace std;
int n,l,r,v[maxn],t[maxn],q[maxn],f[maxn],head=,tail,ans,c[maxn];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
void Dfs(int k){
if(k<=n)c[++c[]]=k;
if(k==)return;
for(int i=max(k-r,);i<=max(k-l,);i++){
if(f[i]+v[k]==f[k]){
Dfs(i);
break;
}
}
}
int main()
{
freopen("iceroad.in","r",stdin);
freopen("iceroad.out","w",stdout);
n=init();l=init();r=init();
for(int i=;i<=n;i++)
v[i]=init();
for(int i=l;i<=n+r;i++){
f[i]=q[head]+v[i];
while(head<=tail&&f[i-l+]>q[tail])tail--;
q[++tail]=f[i-l+];t[tail]=i;
if(t[head]<i-r+)head++;
}
int k=;
for(int i=n+;i<=n+r;i++)
if(f[i]>ans){
ans=f[i];k=i;
}
printf("%d\n",ans);
Dfs(k);
for(int i=c[];i>=;i--)
printf("%d ",c[i]);
printf("-1\n");
return ;
}
题目描述
在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。
输入输出格式
输入格式：
第1行：两个正整数N,M
第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。
输出格式：
第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。
第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。
输入输出样例
5 5
1 2 1
1 3 2
2 4 2
5 1 2
3 5 1
3
1 3 5
说明
对于60%的数据：N <= 200且M <= 10,000
对于100%的数据：N <= 5,000且M <= 50,000
Tarjan：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
#define maxn 50010
using namespace std;
int n,m,head[maxn],num,dfn[maxn],low[maxn],f[maxn],topt,sum,ans[maxn];
struct node{
int v,pre;
}e[maxn*];
stack<int>s;
vector<int>G[maxn/];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
void Add(int from,int to){
num++;e[num].v=to;
e[num].pre=head[from];
head[from]=num;
}
void Dfs(int u){
dfn[u]=low[u]=++topt;
f[u]=;s.push(u);
for(int i=head[u];i;i=e[i].pre){
int v=e[i].v;
if(dfn[v]==){
Dfs(v);low[u]=min(low[u],low[v]);
}
else if(f[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
sum++;
while(u!=s.top()){
f[s.top()]=;G[sum].push_back(s.top());s.pop();
}
f[s.top()]=;G[sum].push_back(s.top());s.pop();
}
}
int main()
{
freopen("classroom.in","r",stdin);
freopen("classroom.out","w",stdout);
n=init();m=init();
int u,v,t;
for(int i=;i<=m;i++){
u=init();v=init();t=init();
Add(u,v);
if(t==)Add(v,u);
}
for(int i=;i<=n;i++)
if(dfn[i]==)Dfs(i);
int mxx=;
for(int i=;i<=sum;i++){
sort(G[i].begin(),G[i].end());
if(mxx<G[i].size())mxx=G[i].size();
}
printf("%d\n",mxx);
memset(ans,,sizeof(ans));
for(int i=;i<=sum;i++)
if(mxx==G[i].size()){
int falg=;
for(int j=;j<mxx;j++){
if(G[i][j]<ans[j]){falg=;break;}
if(G[i][j]>ans[j])break;
}
if(falg)for(int j=;j<mxx;j++)
ans[j]=G[i][j];
}
for(int i=;i<mxx;i++)
printf("%d ",ans[i]);
return ;
}
conclusion
今天题太简单了 准备好AK的
但是吧 数组开小了 这尼玛很打脸
T1模拟
T2高精除 然而高精除高精并不自信 间接写了二分+乘
T3线段树优化dp 数组开小 QAQ
T4 Tarjab模板 数组数组数组数组！！！！ 还有就是T3也可以单调队列优化
考试的时候也想来 也想过优先队列
但是脑抽全都否了....
最后选了常数大的线段树
我是zhizhangQAQ