題解報告三

删除重複資料(dels)

問題描述：

輸入n(≤10000)個無序的正整數ai(≤10000)，将相同的數删除之後隻保留一個，按原順序輸出處理之後的序列。

輸入格式：

第一行為n，第二行為以空格隔開的n個正整數。

輸出格式：

處理之後的資料序列，每個數以空格隔開。

輸入樣例	輸出樣例
6 1 4 3 2 4 1	1 4 3 2

數字根(root)

問題描述：

一個正整數的數字根是它所有數字的和，如果這個結果是一位數，則計算結束，否則繼續計算直到一位數為止。

輸入格式：

一個整數n。(n≤1010000)。

輸出格式：

一個整數k，表示n的數字根。

輸入樣例	輸出樣例
24	6
123456789	9

字母項鍊（necklace）

問題描述：

字母項鍊是由一串A = a1a2 ... am序列組成，m表示制成項鍊的珠子的個數。當項鍊圍成一圈時，最後一個字母am就是a1的前驅（前一個）。第i個珠子比第j個珠子更容易斷裂就是說序列aiai+1 ... ana1 ... ai-1的字典序小于序列ajaj+1 ... ana1 ... aj-1的字典序。序列a1a2 ... an的字典序小于序列b1b2 ... bn的字典序就是存在一個整數i(≤n), 對于每個j(1≤j < i)都要有aj=bj且ai < bi。程式設計找出最容易斷裂的地方。

輸入格式：

第一行為正整數t(≤5)，表示資料組數；每組資料中，第一行為正整數m（10≤m≤10000），表示組成項鍊的字母長度，第二行為組成項鍊的字母序，每個珠子由一個英語的小寫字母表示（a-z）。

輸出格式：

對于每組資料，輸出項鍊最壞連接配接處字母珠子的編号i，表示A[i]就是n個可能斷裂點的字典序最小的地方。如果有不止一個的解，輸出最小的i。

輸入樣例	輸出樣例
2 11 amandamanda 20 afdaksdjfoijaakjlkpq	11 13

平方和分解(squares)

問題描述：

John喜歡研究數字，他把一些連續整數的平方和累加起來，例如：212+222+232+242=2030，然後他又發現：252+262+272=2030。現在他把這個問題反過來看，給定一個正整數n，能否把n分解成若幹個連續的正整數的平方和。John發現有時數字太大，他無法驗證，請你程式設計幫助他驗證這個分解式。

輸入格式：

僅一個正整數n(≤1014)。

輸出格式：

第一行是分解方案數t；接下來t行，每行表示一個解，每個解隻要輸出連續的第一個數a和最後一個數b。按a值大小的升序輸出。如果不能分解，直接輸出1個0。

輸入樣例	輸入樣例
2030	2 21 24 25 27

第一題删除重複資料

這道題沒商量就是桶排

第二題數字根

這道題隻要題目看懂模拟題，不要被資料範圍驚到

什麼是數字根？就是所有位上的數字之和

然後每次都加，知道<10位置

第三題字母項鍊

一.題目大意

表層的題目是說，對于所有得到的子串，隻要字典序更小就更容易斷裂，那麼最容易斷裂的斷點？

實際上就是這個環上的所有子串中字典序最小的

而string定義了字典序

二.算法思路

如何周遊斷開環的所有方法

1.斷環為鍊枚舉起始

2.string活學活用substr拼接

然後去ans最小值*注意事項string型的最小值

三.代碼實作

#include<bits/stdc++.h>
using namespace std;

string a,b,ans;
int ad,n,t;

int main(){
    freopen("necklace.in","r",stdin);
    freopen("necklace.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        scanf("%d\n",&n);
        getline(cin,a);
        ans=a;
        for(int i=1;i<n;i++){
            b=a.substr(i,n-i)+a.substr(0,i);
            if(b<ans)ans=b,ad=i;
        }
        printf("%d\n",ad+1);
    }
    return 0;
}
           

第四題連續平方和

0分算法：國小奧數題，1^2+2^2+....+n^2=(n+1)*n*(2n+1)/6,然後枚舉起始點i計算，枚舉起始點j計算然後。。。10^14呵呵呵呵

一.題目大意

要求找到所有的i,j使得i^2+...+j^2等于n的個數以及輸出

二.算法思路

我們發現為什麼0分算法0分？

因為有很多無用計算

因為枚舉i~j和枚舉i~j+1的算法他是分成兩次完全不懂的問題解決的

是以我們可以直接從i~j發展到i~j+1

然後這種算法叫做尺取法

就時雙指針，i~j如果<nj++，如果>ni++;

三.代碼實作

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1000005;

ll n,tmp,i,j,a[N][2];
int cnt;

int main(){
    freopen("squares.in","r",stdin);
    freopen("squares.out","w",stdout);
    scanf("%lld",&n);
    i=1,j=1,tmp=0;
    while(j*j<=n){
        if(tmp>n)tmp-=i*i,i++;
        else if(tmp<n)tmp+=j*j,j++;
        else {
            a[++cnt][0]=i,a[cnt][1]=j-1;tmp+=j*j;j++;
        }
    }
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++){
        printf("%d %d\n",a[i][0],a[i][1]);
    }
    return 0;
}