标签存档：水题

【链接】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- –

 

【题目链接】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";
}
}
}

【题目链接】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);
}

【题目链接】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;
}

【题目链接】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< }
}