[codeforces 69C]【字符串模拟】

【链接】http://www.codeforces.com/problemset/problem/69/C

【其它】

其实这题很水- -,但是我STL套得很泪流满面...

比如这样

        cin >> S;

        S.erase(S.size()-1);

        Name=S;

        getline(cin,S);

        Del_dot(S);

        stringstream sin(S);

        int Num;

        Tv.clear();

        while (sin >> S >> Num)

              Tv.push_back(make_pair(S,Num));

        pf.push_back(make_pair(Name,Tv));

再比如这样

     for (vector< pair < string, vector < pair

搞了80行,压力太大了。

ym watashi的ruby和叉姐的python- -

 

[JSOI2008]最大数maxnumber 【线段树】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1012
【算法分析】
线段树,会的人都知道。。。
【其它】1Y。用cin果断跑到几乎最慢
【做题原因】邻近省选,练练手,刷出1Y,刷出自信。
【CODE】
#include #include #include #include using namespace std;
const int INF=0x7FFFFFFF;
struct Node{int l,r,key;}Tr[1000000];
int m,mod,n,ans;

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r; Tr[p].key=-INF;
if (l int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
}

void Add(int p,int t,int key){
if (Tr[p].l==Tr[p].r){
Tr[p].key=key;
return;
}
if (t<=(Tr[p].l+Tr[p].r)/2) Add(p*2,t,key);
else Add(p*2+1,t,key);
Tr[p].key=max(Tr[p*2].key,Tr[p*2+1].key);
}

void Get(int p,int l,int r){
if (l<=Tr[p].l && Tr[p].r<=r){
ans=max(ans,Tr[p].key);
return;
}
int mid=(Tr[p].l+Tr[p].r)/2;
if (l<=mid) Get(p*2,l,r);
if (r> mid) Get(p*2+1,l,r);
}

int main(){
ios::sync_with_stdio(false);
ans=n=0;
cin >> m >> mod;
build(1,1,m);
for (int i=1;i<=m;i++){
char ch; __int64 x;
cin >> ch >> x;
if (ch=='A'){
x=(x+ans)%mod;
n++;
Add(1,n,(int)(x));
}
else{
ans=-INF;
Get(1,n-x+1,n);
cout << ans << "n";
}
}
}

[BeiJing2010]取数游戏 game 【水水更健康】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1978

【算法分析】

看到2<=ai<=10^6。

就可以开个桶暴力了。

公约数首先是约数嘛。。。然后就把他所有的约数搞一下,瞬间AC。

【时间复杂度】O(n * Ai ^ 0.5)

【空间复杂度】O(10^6)

【CODE】

#include int p[1000005];

int main(){ freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&L);
    for (i=1;i<=n;i++){
        scanf("%d",&x);
        if (x        now=0;
        for (j=1;j*j<=x;j++)
          if (!(x%j)){
            if (j>=L) now>?=p[j];
            if (x/j>=L) now>?=p[x/j];
          }
        now++;
        ans>?=now;
        for (j=1;j*j<=x;j++)
          if (!(x%j)){
            p[j]=now;
            p[x/j]=now;
          }
    }
    printf("%dn",ans);
}

[ZJOI2010 count 数字计数]统计

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1833
【算法分析】
就是从高到低枚举每一位,然后试填比它原位小的数,然后后面的位就可以随便填。这个随便填的话,显然000...000到999...999这一连串中,0-9的数量肯定是一样的。
所以每一位分别+上 (999..999+1)*log (999.999+1)/10。
利用这个快速算,很容易就得解。
【其它】比较繁琐= =,WA了几次。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
lld L[10];
lld a[10],b[10];
void f(lld x,lld *res){
int i,j,Log=0;
memset(L,0,sizeof(L));
lld mul=1;
while (mul<=x){
mul*=10;
Log++;
}
mul/=10; Log--;
while (mul){
for (i=1;i res[i]+=mul;
for (j=0;j<10;j++){
res[j]+=L[j]*mul;
res[j]+=mul*Log/10;
}
}
L[x/mul%10]++;
mul/=10;
Log--;
if (mul){
for (i=1;i<10;i++){
res[i]+=mul;
for (j=0;j<10;j++)
res[j]+=mul*Log/10;
}
if (x/mul%10){
for (i=0;i<10;i++){
res[i]+=mul*Log/10;
res[i]+=L[i]*mul;
}
res[0]+=mul;
}
}
}
}

int main(){
lld x,y;
cin >> x >> y;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
f(x,a);
f(y+1,b);
for (int i=0;i<10;i++)
cout << b[i]-a[i] << " ";
cout << endl;
}

[COCI 2009/2010 - Constest #7 COKOLADA]对二进制数的理解

【题目链接】http://evaluator.hsin.hr/login.php?redirect=index.php
【题目大意】
给出一个尺寸N。
你需要取一个2^k (k是任你选的)的巧克力出来,然后切若干刀(每刀把一个巧克力切开成两半一样大小的)
最终在其中取出若干个块巧克力,使得加起来的尺寸等于N。
最终输出2^k和切得刀数。
在保证2^k最小的前提下,切刀数要最少。
【算法分析】
同属于被秒杀题= =
假如N=2^k,那么直接输出  2^k 0
否则输出最小的一个k满足,N<2^k (用log2求就可以了),
然后输出将n变成二进制以后从个位数上去的第一个“1”和k的差即可。
【其它】
YY一下就懂了。
【CODE】
#include #include #include int n,LG,i;
scanf("%d",&n);
LG=(int)(log(n)/log(2)+1e-7);
if (1< else{
LG++;
i=0;
while (n%2==0){
i++;
n/=2;
}
printf("%d %dn",1< }
}