[Android] Chèn ảnh động *.gif trong Android

Tạo một ứng dụng Android và đặt tên là AnimationGif với Activity chính là MainActivity.
Tiếp theo, ta copy một hình ảnh có định dạng *.gif vào trong thư mục /assets. Ở đây mình sẽ sử dụng tập tin test.gif.

Cách 1: Sử dụng GifDecoderView

Để hiển thị được ảnh dạng *.gif, chúng ta sẽ sử dụng một custom view có tên là GifDecoderView, và cần một class để decode tập tin *.gif, có tên là GifDecoder.


GifDecoder.java

public class GifDecoder {
        /**
         * File read status: No errors.
         */
        public static final int STATUS_OK = 0;
        /**
         * File read status: Error decoding file (may be partially decoded)
         */
        public static final int STATUS_FORMAT_ERROR = 1;
        /**
         * File read status: Unable to open source.
         */
        public static final int STATUS_OPEN_ERROR = 2;
        /** max decoder pixel stack size */
        protected static final int MAX_STACK_SIZE = 4096;
        protected InputStream in;
        protected int status;
        protected int width; // full image width
        protected int height; // full image height
        protected boolean gctFlag; // global color table used
        protected int gctSize; // size of global color table
        protected int loopCount = 1; // iterations; 0 = repeat forever
        protected int[] gct; // global color table
        protected int[] lct; // local color table
        protected int[] act; // active color table
        protected int bgIndex; // background color index
        protected int bgColor; // background color
        protected int lastBgColor; // previous bg color
        protected int pixelAspect; // pixel aspect ratio
        protected boolean lctFlag; // local color table flag
        protected boolean interlace; // interlace flag
        protected int lctSize; // local color table size
        protected int ix, iy, iw, ih; // current image rectangle
        protected int lrx, lry, lrw, lrh;
        protected Bitmap image; // current frame
        protected Bitmap lastBitmap; // previous frame
        protected byte[] block = new byte[256]; // current data block
        protected int blockSize = 0; // block size last graphic control extension info
        protected int dispose = 0; // 0=no action; 1=leave in place; 2=restore to bg; 3=restore to prev
        protected int lastDispose = 0;
        protected boolean transparency = false; // use transparent color
        protected int delay = 0; // delay in milliseconds
        protected int transIndex; // transparent color index
        // LZW decoder working arrays
        protected short[] prefix;
        protected byte[] suffix;
        protected byte[] pixelStack;
        protected byte[] pixels;
        protected Vector frames; // frames read from current file
        protected int frameCount;

        private static class GifFrame {
                public GifFrame(Bitmap im, int del) {
                        image = im;
                        delay = del;
                }

                public Bitmap image;
                public int delay;
        }

        /**
         * Gets display duration for specified frame.
         *
         * @param n
         *          int index of frame
         * @return delay in milliseconds
         */
        public int getDelay(int n) {
                delay = -1;
                if ((n >= 0) && (n < frameCount)) {
                        delay = frames.elementAt(n).delay;
                }
                return delay;
        }

        /**
         * Gets the number of frames read from file.
         *
         * @return frame count
         */
        public int getFrameCount() {
                return frameCount;
        }

        /**
         * Gets the first (or only) image read.
         *
         * @return BufferedBitmap containing first frame, or null if none.
         */
        public Bitmap getBitmap() {
                return getFrame(0);
        }

        /**
         * Gets the "Netscape" iteration count, if any. A count of 0 means repeat indefinitiely.
         *
         * @return iteration count if one was specified, else 1.
         */
        public int getLoopCount() {
                return loopCount;
        }

        /**
         * Creates new frame image from current data (and previous frames as specified by their disposition codes).
         */
        protected void setPixels() {
                // expose destination image's pixels as int array
                int[] dest = new int[width * height];
                // fill in starting image contents based on last image's dispose code
                if (lastDispose > 0) {
                        if (lastDispose == 3) {
                                // use image before last
                                int n = frameCount - 2;
                                if (n > 0) {
                                        lastBitmap = getFrame(n - 1);
                                } else {
                                        lastBitmap = null;
                                }
                        }
                        if (lastBitmap != null) {
                                lastBitmap.getPixels(dest, 0, width, 0, 0, width, height);
                                // copy pixels
                                if (lastDispose == 2) {
                                        // fill last image rect area with background color
                                        int c = 0;
                                        if (!transparency) {
                                                c = lastBgColor;
                                        }
                                        for (int i = 0; i < lrh; i++) {
                                                int n1 = (lry + i) * width + lrx;
                                                int n2 = n1 + lrw;
                                                for (int k = n1; k < n2; k++) {
                                                        dest[k] = c;
                                                }
                                        }
                                }
                        }
                }
                // copy each source line to the appropriate place in the destination
                int pass = 1;
                int inc = 8;
                int iline = 0;
                for (int i = 0; i < ih; i++) {
                        int line = i;
                        if (interlace) {
                                if (iline >= ih) {
                                        pass++;
                                        switch (pass) {
                                        case 2:
                                                iline = 4;
                                                break;
                                        case 3:
                                                iline = 2;
                                                inc = 4;
                                                break;
                                        case 4:
                                                iline = 1;
                                                inc = 2;
                                                break;
                                        default:
                                                break;
                                        }
                                }
                                line = iline;
                                iline += inc;
                        }
                        line += iy;
                        if (line < height) {
                                int k = line * width;
                                int dx = k + ix; // start of line in dest
                                int dlim = dx + iw; // end of dest line
                                if ((k + width) < dlim) {
                                        dlim = k + width; // past dest edge
                                }
                                int sx = i * iw; // start of line in source
                                while (dx < dlim) {
                                        // map color and insert in destination
                                        int index = ((int) pixels[sx++]) & 0xff;
                                        int c = act[index];
                                        if (c != 0) {
                                                dest[dx] = c;
                                        }
                                        dx++;
                                }
                        }
                }
                image = Bitmap.createBitmap(dest, width, height, Config.ARGB_4444);
        }

        /**
         * Gets the image contents of frame n.
         *
         * @return BufferedBitmap representation of frame, or null if n is invalid.
         */
        public Bitmap getFrame(int n) {
                if (frameCount <= 0)
                        return null;
                n = n % frameCount;
                return ((GifFrame) frames.elementAt(n)).image;
        }

        /**
         * Reads GIF image from stream
         *
         * @param is
         *          containing GIF file.
         * @return read status code (0 = no errors)
         */
        public int read(InputStream is) {
                init();
                if (is != null) {
                        in = is;
                        readHeader();
                        if (!err()) {
                                readContents();
                                if (frameCount < 0) {
                                        status = STATUS_FORMAT_ERROR;
                                }
                        }
                } else {
                        status = STATUS_OPEN_ERROR;
                }
                try {
                        is.close();
                } catch (Exception e) {
                }
                return status;
        }

        /**
         * Decodes LZW image data into pixel array. Adapted from John Cristy's BitmapMagick.
         */
        protected void decodeBitmapData() {
                int nullCode = -1;
                int npix = iw * ih;
                int available, clear, code_mask, code_size, end_of_information, in_code, old_code, bits, code, count, i, datum, data_size, first, top, bi, pi;
                if ((pixels == null) || (pixels.length < npix)) {
                        pixels = new byte[npix]; // allocate new pixel array
                }
                if (prefix == null) {
                        prefix = new short[MAX_STACK_SIZE];
                }
                if (suffix == null) {
                        suffix = new byte[MAX_STACK_SIZE];
                }
                if (pixelStack == null) {
                        pixelStack = new byte[MAX_STACK_SIZE + 1];
                }
                // Initialize GIF data stream decoder.
                data_size = read();
                clear = 1 << data_size;
                end_of_information = clear + 1;
                available = clear + 2;
                old_code = nullCode;
                code_size = data_size + 1;
                code_mask = (1 << code_size) - 1;
                for (code = 0; code < clear; code++) {
                        prefix[code] = 0;
                        suffix[code] = (byte) code;
                }
                // Decode GIF pixel stream.
                datum = bits = count = first = top = pi = bi = 0;
                for (i = 0; i < npix;) {
                        if (top == 0) {
                                if (bits < code_size) {
                                        // Load bytes until there are enough bits for a code.
                                        if (count == 0) {
                                                // Read a new data block.
                                                count = readBlock();
                                                if (count <= 0) {
                                                        break;
                                                }
                                                bi = 0;
                                        }
                                        datum += (((int) block[bi]) & 0xff) << bits;
                                        bits += 8;
                                        bi++;
                                        count--;
                                        continue;
                                }
                                // Get the next code.
                                code = datum & code_mask;
                                datum >>= code_size;
                                bits -= code_size;
                                // Interpret the code
                                if ((code > available) || (code == end_of_information)) {
                                        break;
                                }
                                if (code == clear) {
                                        // Reset decoder.
                                        code_size = data_size + 1;
                                        code_mask = (1 << code_size) - 1;
                                        available = clear + 2;
                                        old_code = nullCode;
                                        continue;
                                }
                                if (old_code == nullCode) {
                                        pixelStack[top++] = suffix[code];
                                        old_code = code;
                                        first = code;
                                        continue;
                                }
                                in_code = code;
                                if (code == available) {
                                        pixelStack[top++] = (byte) first;
                                        code = old_code;
                                }
                                while (code > clear) {
                                        pixelStack[top++] = suffix[code];
                                        code = prefix[code];
                                }
                                first = ((int) suffix[code]) & 0xff;
                                // Add a new string to the string table,
                                if (available >= MAX_STACK_SIZE) {
                                        break;
                                }
                                pixelStack[top++] = (byte) first;
                                prefix[available] = (short) old_code;
                                suffix[available] = (byte) first;
                                available++;
                                if (((available & code_mask) == 0) && (available < MAX_STACK_SIZE)) {
                                        code_size++;
                                        code_mask += available;
                                }
                                old_code = in_code;
                        }
                        // Pop a pixel off the pixel stack.
                        top--;
                        pixels[pi++] = pixelStack[top];
                        i++;
                }
                for (i = pi; i < npix; i++) {
                        pixels[i] = 0; // clear missing pixels
                }
        }

        /**
         * Returns true if an error was encountered during reading/decoding
         */
        protected boolean err() {
                return status != STATUS_OK;
        }

        /**
         * Initializes or re-initializes reader
         */
        protected void init() {
                status = STATUS_OK;
                frameCount = 0;
                frames = new Vector();
                gct = null;
                lct = null;
        }

        /**
         * Reads a single byte from the input stream.
         */
        protected int read() {
                int curByte = 0;
                try {
                        curByte = in.read();
                } catch (Exception e) {
                        status = STATUS_FORMAT_ERROR;
                }
                return curByte;
        }

        /**
         * Reads next variable length block from input.
         *
         * @return number of bytes stored in "buffer"
         */
        protected int readBlock() {
                blockSize = read();
                int n = 0;
                if (blockSize > 0) {
                        try {
                                int count = 0;
                                while (n < blockSize) {
                                        count = in.read(block, n, blockSize - n);
                                        if (count == -1) {
                                                break;
                                        }
                                        n += count;
                                }
                        } catch (Exception e) {
                                e.printStackTrace();
                        }
                        if (n < blockSize) {
                                status = STATUS_FORMAT_ERROR;
                        }
                }
                return n;
        }

        /**
         * Reads color table as 256 RGB integer values
         *
         * @param ncolors
         *          int number of colors to read
         * @return int array containing 256 colors (packed ARGB with full alpha)
         */
        protected int[] readColorTable(int ncolors) {
                int nbytes = 3 * ncolors;
                int[] tab = null;
                byte[] c = new byte[nbytes];
                int n = 0;
                try {
                        n = in.read(c);
                } catch (Exception e) {
                        e.printStackTrace();
                }
                if (n < nbytes) {
                        status = STATUS_FORMAT_ERROR;
                } else {
                        tab = new int[256]; // max size to avoid bounds checks
                        int i = 0;
                        int j = 0;
                        while (i < ncolors) {
                                int r = ((int) c[j++]) & 0xff;
                                int g = ((int) c[j++]) & 0xff;
                                int b = ((int) c[j++]) & 0xff;
                                tab[i++] = 0xff000000 | (r << 16) | (g << 8) | b;
                        }
                }
                return tab;
        }

        /**
         * Main file parser. Reads GIF content blocks.
         */
        protected void readContents() {
                // read GIF file content blocks
                boolean done = false;
                while (!(done || err())) {
                        int code = read();
                        switch (code) {
                        case 0x2C: // image separator
                                readBitmap();
                                break;
                        case 0x21: // extension
                                code = read();
                                switch (code) {
                                case 0xf9: // graphics control extension
                                        readGraphicControlExt();
                                        break;
                                case 0xff: // application extension
                                        readBlock();
                                        String app = "";
                                        for (int i = 0; i < 11; i++) {
                                                app += (char) block[i];
                                        }
                                        if (app.equals("NETSCAPE2.0")) {
                                                readNetscapeExt();
                                        } else {
                                                skip(); // don't care
                                        }
                                        break;
                                case 0xfe:// comment extension
                                        skip();
                                        break;
                                case 0x01:// plain text extension
                                        skip();
                                        break;
                                default: // uninteresting extension
                                        skip();
                                }
                                break;
                        case 0x3b: // terminator
                                done = true;
                                break;
                        case 0x00: // bad byte, but keep going and see what happens break;
                        default:
                                status = STATUS_FORMAT_ERROR;
                        }
                }
        }

        /**
         * Reads Graphics Control Extension values
         */
        protected void readGraphicControlExt() {
                read(); // block size
                int packed = read(); // packed fields
                dispose = (packed & 0x1c) >> 2; // disposal method
                if (dispose == 0) {
                        dispose = 1; // elect to keep old image if discretionary
                }
                transparency = (packed & 1) != 0;
                delay = readShort() * 10; // delay in milliseconds
                transIndex = read(); // transparent color index
                read(); // block terminator
        }

        /**
         * Reads GIF file header information.
         */
        protected void readHeader() {
                String id = "";
                for (int i = 0; i < 6; i++) {
                        id += (char) read();
                }
                if (!id.startsWith("GIF")) {
                        status = STATUS_FORMAT_ERROR;
                        return;
                }
                readLSD();
                if (gctFlag && !err()) {
                        gct = readColorTable(gctSize);
                        bgColor = gct[bgIndex];
                }
        }

        /**
         * Reads next frame image
         */
        protected void readBitmap() {
                ix = readShort(); // (sub)image position & size
                iy = readShort();
                iw = readShort();
                ih = readShort();
                int packed = read();
                lctFlag = (packed & 0x80) != 0; // 1 - local color table flag interlace
                lctSize = (int) Math.pow(2, (packed & 0x07) + 1);
                // 3 - sort flag
                // 4-5 - reserved lctSize = 2 << (packed & 7); // 6-8 - local color
                // table size
                interlace = (packed & 0x40) != 0;
                if (lctFlag) {
                        lct = readColorTable(lctSize); // read table
                        act = lct; // make local table active
                } else {
                        act = gct; // make global table active
                        if (bgIndex == transIndex) {
                                bgColor = 0;
                        }
                }
                int save = 0;
                if (transparency) {
                        save = act[transIndex];
                        act[transIndex] = 0; // set transparent color if specified
                }
                if (act == null) {
                        status = STATUS_FORMAT_ERROR; // no color table defined
                }
                if (err()) {
                        return;
                }
                decodeBitmapData(); // decode pixel data
                skip();
                if (err()) {
                        return;
                }
                frameCount++;
                // create new image to receive frame data
                image = Bitmap.createBitmap(width, height, Config.ARGB_4444);
                setPixels(); // transfer pixel data to image
                frames.addElement(new GifFrame(image, delay)); // add image to frame
                // list
                if (transparency) {
                        act[transIndex] = save;
                }
                resetFrame();
        }

        /**
         * Reads Logical Screen Descriptor
         */
        protected void readLSD() {
                // logical screen size
                width = readShort();
                height = readShort();
                // packed fields
                int packed = read();
                gctFlag = (packed & 0x80) != 0; // 1 : global color table flag
                // 2-4 : color resolution
                // 5 : gct sort flag
                gctSize = 2 << (packed & 7); // 6-8 : gct size
                bgIndex = read(); // background color index
                pixelAspect = read(); // pixel aspect ratio
        }

        /**
         * Reads Netscape extenstion to obtain iteration count
         */
        protected void readNetscapeExt() {
                do {
                        readBlock();
                        if (block[0] == 1) {
                                // loop count sub-block
                                int b1 = ((int) block[1]) & 0xff;
                                int b2 = ((int) block[2]) & 0xff;
                                loopCount = (b2 << 8) | b1;
                        }
                } while ((blockSize > 0) && !err());
        }

        /**
         * Reads next 16-bit value, LSB first
         */
        protected int readShort() {
                // read 16-bit value, LSB first
                return read() | (read() << 8);
        }

        /**
         * Resets frame state for reading next image.
         */
        protected void resetFrame() {
                lastDispose = dispose;
                lrx = ix;
                lry = iy;
                lrw = iw;
                lrh = ih;
                lastBitmap = image;
                lastBgColor = bgColor;
                dispose = 0;
                transparency = false;
                delay = 0;
                lct = null;
        }

        /**
         * Skips variable length blocks up to and including next zero length block.
         */
        protected void skip() {
                do {
                        readBlock();
                } while ((blockSize > 0) && !err());
        }
}

GifDecoderView.java

public class GifDecoderView extends ImageView {

	public GifDecoderView(Context context) {
		super(context);
	}

	public GifDecoderView(Context context, InputStream stream) {
		super(context);
		playGif(stream);
	}

	private boolean mIsPlayingGif = false;

	private GifDecoder mGifDecoder;

	private Bitmap mTmpBitmap;

	final Handler mHandler = new Handler();

	final Runnable mUpdateResults = new Runnable() {
		public void run() {
			if (mTmpBitmap != null && !mTmpBitmap.isRecycled()) {
				GifDecoderView.this.setImageBitmap(mTmpBitmap);
			}
		}
	};

	private void playGif(InputStream stream) {
		mGifDecoder = new GifDecoder();
		mGifDecoder.read(stream);

		mIsPlayingGif = true;

		new Thread(new Runnable() {
			public void run() {
				final int n = mGifDecoder.getFrameCount();
				final int ntimes = mGifDecoder.getLoopCount();
				int repetitionCounter = 0;
				do {
					for (int i = 0; i < n; i++) {
						mTmpBitmap = mGifDecoder.getFrame(i);
						int t = mGifDecoder.getDelay(i);
						mHandler.post(mUpdateResults);
						try {
							Thread.sleep(t);
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
					}
					if (ntimes != 0) {
						repetitionCounter++;
					}
				} while (mIsPlayingGif && (repetitionCounter <= ntimes));
			}
		}).start();
	}

	public void stopRendering() {
		mIsPlayingGif = true;
	}
}

Tiếp theo, ta chỉnh sửa MainActivity để hiển thị tập tin test.gif.
Chúng ta đọc tập tin test.gif vào trong một InputStream

		InputStream stream = null;
		try {
			stream = getAssets().open("test.gif");
		} catch (IOException e) {
			e.printStackTrace();
		}

Sau đó khởi tạo một GifDecoderView với tham số là InputStream vừa có như sau

		GifDecoderView view = new GifDecoderView(this, stream);

Cuối cùng là gán nội dung vào view của Activity để hiển thị:

		setContentView(view);

Cách 2: Sử dụng GifWebView

Cách này, chúng ta sẽ sử dụng GifWebView. Thực tế, ở đây ta sử dụng WebView, chỉ là custom lại để hiển thị ảnh từ đường dẫn đưa vào.
Tạo một class GifWebView với nội dung sau.

public class GifWebView extends WebView {

	public GifWebView(Context context, String path) {
		super(context);
		loadUrl(path);
	}
}

Sau đó, chỉnh sửa lại MainActivity. Chúng ta chỉ cần một đoạn mã sau để hiển thị test.gif

		GifWebView view = new GifWebView(this,"file:///android_asset/test.gif");

Và gán view này để hiển thị trên thiết bị:

		setContentView(view);

Đọc dữ liệu từ file text trong Java

Trước khi học bài này bạn nên đọc lại bài:

Để hiểu rõ về cách Java đọc dữ liệu một chút vì nó rất quan trọng nếu bạn không hiểu rõ cái này thì sẽ mãi không làm chủ được Java đâu 🙂

Tổng quan

doc-du-lieu-yeulaptrinh.pw

Các luồng và class trong I/O file text

Nhắc lại nguyên lý đọc dữ liệu trong Java một chút: các thiết bị vào ra (bàn phím, màn hình…) qua luồng rồi ta mới nhận được thông tin.

 luong-trong-doc-file-yeulaptrinh.pwSử dụng BufferedReader BufferedWriter

Đọc, ghi file với BufferedReader và BufferedWriter là cách đọc nhanh nhất trong Java, ngoài ra nó còn có nhiều tính năng có sẵn kèm theo như: đọc cả dòng, encoding… Có nhiều cách đọc, ghi file nhưng mình khuyên các bạn nên dùng cách này dù nó có dài hơn một chút (code bên dưới).

import java.io.*;
import java.util.*;

public class ReadTest2
{
	static long total = 0;

	private static void ReadLines() {
		try {
			String s = "";
			BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
			while (stdin.ready()) {
				s = stdin.readLine();
				for (int i=0; i

Sử dụng FileReader và FileWriter

Thằng này thì không hỗ trợ đọc từng dòng, mã hóa và nó làm việc với bảng mã mặc định của hệ thống nên nó không phải là cách tốt để đọc và ghi file.

static void copyFile(FileReader inputFile, FileWriter outputFile) {
try{
  // Read the first character.
  int nextChar = inputFile.read();
  // Have we reached the end of file?
  while(nextChar != -1) {
    outputFile.write(nextChar);
    // Read the next character.
    nextChar = inputFile.read();
  }
  outputFile.flush();
}
catch(IOException e) {  System.out.println("Unable to copy file");
}
}

PALINY – spoj

Đề bài:

Thuật toán:

Chặt nhị phần + Hash

Code:

{$H+}
uses math;
const
  fi='';//paliny.inp';
  fo='';//paliny.out';
  maxn=50003;
  pp=307;
  base=trunc(1e9)+7;
var
  i,j,n,d,c,g,top,ans : longint;
  ha,hb,pow : array[0..maxn] of int64;
  a : array[1..maxn] of longint;
  s : string;
function gethash1(l,r : longint) : int64;
  begin
    gethash1 := (ha[r] - ha[l-1] * pow[r-l+1] + base * base) mod base;
  end;
function gethash2(l,r : longint) : int64;
  begin
    gethash2 := (hb[r] - hb[l+1] * pow[l-r+1] + base * base) mod base;
  end;
function ok ( le : longint) : boolean;
  var i,j : longint;
  begin
    for i := 1 to n - le + 1 do
      if gethash1(i,i+le-1) = gethash2(i+le-1,i) then exit(true);
    exit(false);
  end;
procedure process;
  begin
  d := 1 ;
  c := top ;
  g := (d+c) div 2;
  while (G<>d) and (g<>C) do
    begin
      if ok (a[g]) then d := g else c := g;
      g := (d+c) div 2;
    end;
  for g := c downto d do
    if ok (a[g]) then
      begin
        ans := max(ans,a[g]);
        exit;
      end;
  end;
procedure push(x : longint);
  begin
    inc(top);
    a[top] := x;
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(n);
  readln(s);
  pow[0] := 1;
  for i := 1 to n do pow[i] := pow[i-1] * pp mod base;
  for i := 1 to n do ha[i] := ( ha[i-1] * pp + ord(s[i]) ) mod base;
  for i := n downto 1 do hb[i] := ( hb[i+1] * pp + ord(s[i]) ) mod base;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 0 then push(i);
  process;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 1 then push(i);
  process;
  writeln(ans);
  close(input);close(output);
end.

Đặt tên biến trong Java

Nhiều bạn học ngôn ngữ lập trình nhưng vẫn còn đặt tên biến chưa đúng, sai so với quy ước chung. Hôm nay mình sẽ chia sẻ với các bạn cách đặt tên trong Java nói riêng và trong lập trình nói chung một cách đúng, chuẩn nhất.

Khái niệm định danh là gì?

Định danh là một xâu ký tự thể hiện tên các biến, các phương thức, các lớp và nhãn

Định danh là tên của biến ví dụ như: i, j, a, b, s, ans, value…

Định danh là tên của phương thức ví dụ như: getName(), setTime(), goHome()…

Quy định về định danh:wrong-java-yeulaptrinh-pw

  • Các ký tự có thể là chữ số, chữ cái, ‘$’ hoặc ‘_’.
  • Tên không được phép:
    • Bắt đầu bởi một chữ số.
    • Trùng với từ khóa.
  • Phân biệt chữ hoa chữ thường.http://yeulaptrinh.de/wp-content/uploads/2017/01/correct-java-yeulaptrinh.pw_-1-1.png
    • Yourname, yourname, YourName và yourName là 4 định danh khác nhau.

 

Quy ước với định danh (naming convention):

  • Bắt đầu bằng chữ cái.
  • Gói (package): tất cả sử dụng chữ thường.
    • theexample
  • Lớp (Class): viết hoa chữ cái đầu tiên trong các từ ghép lại.
    • TheExample
  • Phương thức/thuộc tính (method/field): Bắt đầu bằng chữ thường, viết hoa chữ cái đầu tiên trong các từ còn lại.
    • theExample
  • Hằng (constants): Tất cả viết hoa.
    • THE_EXAMPLE

 

Những từ không được đặt tên cho biến, hàm…

  • Literals (từ đã được định nghĩa):
    null, true, false.
  • Từ khóa (keyword)
    abstract assert boolean break byte case 
    catch char class continue default do double 
    else extends final finally float for if 
    implements import instanceof int interface 
    long native new package private protected 
    public return short static strictfp super 
    switch synchronized this throw throws 
    transient try void volatile while
  • Từ dành riêng (reserved for future use)
    byvalue cast const future generic goto inner
    operator outer rest var volatile

NKSGAME – spoj

Đề bài:

Thuật toán:

Bài yêu cầu với mỗi số [latex]b[i][/latex] tìm [latex]c[j][/latex] sao cho [latex]|b[i]+c[j]|[/latex] nhỏ nhất. Suy ra chọn sao cho [latex]b[i]+c[j][/latex] có giá trị gần [latex]0[/latex] nhất

Thuật toán sẽ là:

  1. Sắp xếp lại mảng [latex]c[][/latex].
  2. Với mỗi [latex]b[i][/latex] tìm kiếm nhị phân [latex]c[j][/latex] thỏa mãn [latex]b[i]+c[j][/latex] có giá trị gần [latex]0[/latex] nhất.

Nếu chưa hiểu rõ bạn có thể xem code bên dưới.

Code:

#include 

using namespace std;

const int maxn = 100009;
const int oo = 2000000009;
int i, j, n, ans, tmp, b[maxn], a[maxn];

bool cmp (int x, int y) {
     return(x < y);
}

int main() {
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i];
    for (i = 1; i <= n; i++) cin >> b[i];
    sort (b+1, b+n+1, cmp);
    ans = oo;
    for (i = 1; i <= n; i++) {
        tmp = lower_bound(b+1,b+n+1,0-a[i]) - b;
        if (tmp > n) tmp = n;
        ans = min(ans, abs(a[i] + b[tmp]));
        if (tmp == 1) continue;
        ans = min(ans, abs(a[i] + b[tmp-1]));
    }
    cout << ans;
    return 0;
}

BCDIV – spoj

Đề bài:

Thuật toán:

Gọi f[i][j] là chia i số vào n nhóm.

  • f[i][j]=f[i-1][j-1]+f[i-1][j]*j.
  • Khởi tạo f[0][0]=1.

Giải thích công thức trên:

  • Nếu đã chia được (i-1) số vào (j-1) nhóm-> bắt buộc phải chia số thứ i vào nhóm thứ j-> có f[i-1][j-1] cách
  • Nếu ta đã chia được (i-1) số vào j nhóm->có j cách để cho số thứ i vào một nhóm bắt kì->có f[i-1][j]*j

Tổng cộng có f[i-1][j-1]+f[i-1][j]*j.

Code:

const   fi      ='';
        fo      ='';
var     n, k    :int64;
        f       :array[0..25,0..25] of int64;
        i, j    :longint;
        t       :longint;
begin
        fillchar(F, sizeof(f),0);
        f[0,0]:=1;
        for i:=1 to 25 do
                for j:=1 to 25 do
                        f[i,j]:=f[i-1,j-1]+f[i-1,j]*j;
        assign(input,fi);
        reset(input);
        assign(output,fo);
        rewrite(output);
        readln(t);
        for i:=1 to t do
                begin
                        readln(n,k);
                        writeln(f[n,k]);
                end;
        close(input);close(output);
end.

C11STAR – SPOJ

Đề bài:

Thuật toán:

+ 20% test đầu với m, n ≤100:

– Với dữ liệu nhỏ như thế này ta có thể làm cách thô thiển là duyệt tất cả hình thỏa mãn là ngôi sao rồi tăng kết quả lên.

– Độ phức tạp: O((m*n)^2)

+ 30% test tiếp theo có m≤600, n ≤150:  

– Ở đây ta có thể tiếp cận bài toán theo hướng khác: đếm hình chữ nhật xiên 45 độ.

– Giờ ta nghĩ đến phương pháp quay sao cho quy bài toán về đếm hình chữ nhật, để ý là các ô thuộc cùng đường chéo thì có tổng X=i+j và hiệu Y=i-j giống nhau, từ đó ta có 1 phép biến đổi:

+ biến ô (i,j) thành ô (i+j,i-j) trong bảng mới.

Bây giờ ta có 1 bảng mới với kích thước (m+n)*(m+n) :

+ Gọi f[i][j][‘char’] là số cặp ký tự ‘char’ trong 2 cột i và j.

+ Duyệt O((m+n)^3) để tính mảng f, sau đó dùng O((m+n)^2) để cập nhật kết quả

→ kết quả là Sum(f[i][j][‘char’]*(f[i][j][‘char’]-1)/2);

+ Để ý là các ô có (i+j) mod 2=0. và (i+j) mod 2=1 không liên quan tới nhau, do đó ta có thể đưa về 2 bảng để giảm độ phức tạp 1 tý để ăn được subtask này.

– Độ phức tạp O((m+n)^3)

+ 50% test cuối có m≤3000, n ≤200:

– Ta có các nhận xét sau:

+ Bảng có tối đa (m+n) đường chéo

+ Hình ngôi sao to nhất cũng chỉ nằm trong phạm vi min(m,n)^2

Từ đó ta có cách giải:

+ Gọi f[i][j][‘char’] số cặp ký tự ‘char’ nằm trên 2 đường chéo i và j.

+ Duyệt m*n ô của bảng

+ Với mỗi ô ta duyệt min(m,n) ô cùng đường chéo với nó trở lên, nếu cùng ký tự:

→ tăng kết quả lên f[i][j][‘char’]

→ cập nhật f[i][j][‘char’]=f[i][j][‘char’]+1

– Độ phức tạp O(m*n*min(m,n))

Code:

const   fi      ='';
        fo      ='';
        maxM    =3000;
        maxN    =200;

var     f       :array['a'..'z',1..maxM+maxN,1..maxM+maxN] of integer;
        m, n    :longint;
        a       :array[0..maxM,0..maxN] of char;

procedure Optimize;
var     i, j,i1,j1    :longint;
        ans     :longint;
begin
        fillchar(f,sizeof(f),0);
        ans:=0;
        for i:=1 to m do
                for j:=1 to n do
                        if a[i,j]<>'.' then
                                begin
                                        i1:=i;j1:=j;
                                        while (i1

KVIP – spoj

Đề bài:

Thuật toán:

Giả sử người 1 (VIP) ngồi ở vị trí k1 thì:

– Người 2,3,…,k1-1 sẽ ngồi đúng vị trí của mình: 2,3,…,k1-1

– Người k1 có 2 cách chọn vị trí ngồi:

— Chọn ngồi ở vị trí 1: những người k1+1,k1+2,…,n sẽ ngồi đúng vị trí của mình

— Chọn ngồi ở vị trí k2>k1: người k1+1,k1+2,…,k2-1 sẽ ngồi đúng vị trí

— Người k2 có 2 cách chọn vị trí ngồi:

——– Chọn ngồi ở vị trí 1: những người k1+1,k1+2,…,n sẽ ngồi đúng vị trí của mình

——– Chọn ngồi ở vị trí k3: người k2+1,k2+2,…,k3-1 sẽ ngồi đúng vị trí

……

 

Đề bài quy về chọn 1 dãy các phần tử: k1,k2,k3,…,kx,1 ( với k1<k2<k3…<kx )

Tức là:

– Người 1 ngồi vị trí k1

– Người k1 ngồi vị trí k2

– Người k2 ngồi vị trí k3

– Người kx-1 ngồi vị trí kx

– Người kx ngồi vị trí 1

– Những người còn lại ngồi đúng vị trí của mình

 

Kết quả của dãy đã chọn là:

A[1,1] + A[2,2] + … + A[n,n] – A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1]

Đặt S=A[1,1] + A[2,2] + … + A[n,n], S không đổi

=> Cần tìm dãy sao cho:

(- A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1]) đạt giá trị lớn nhất

Gọi F[i] là tổng lớn nhất của dãy {k1,k2,…,i,1} ( người i ngồi vị trí 1 )

  • F[i] = – A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1] ( với kx=i )
  • F[i] = max ( F[i], F[j] – A[j,1] + A[j,j] + A[i,1] – A[i,i] ) với ( i>j )

Kết quả bài toán: S + F (max)

Code:

uses    math;
const   fi      ='';
        fo      ='';
        maxn    =1000;

var     a       :Array[1..maxN,1..maxN] of longint;
        f       :Array[1..maxN] of int64;
        n       :longint;

procedure Optimize;
var     i , j   :longint;
        ans :int64;
        maxF    :int64;
begin
        f[1]:=0;
        for i:=1 to n do f[1]:=f[1]+a[i,i];
        for i:=2 to n do
                begin
                        f[i]:=low(int64);
                        for j:=i-1 downto 1 do
                                f[i]:=max(f[i],f[j]-a[j,1]+a[j,i]-a[i,i]+a[i,1]);
                end;
        maxF:=f[1];
        for i:=2 to n do maxF:=max(maxF,f[i]);
        writeln(maxF);
end;

procedure run;
var     i, j    :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                for j:=1 to n do read(a[i,j]);
        Optimize;
        close(input);close(output);
end;

begin
        run;
end.

DIFFSTR – spoj

Đề bài:

Thuật toán:

Solution ăn 60%:

Xét xâu S và dãy x[1..n] thỏa mãn 1 <= x[i] <= length(S) và x[i] > x[i – 1]. Với mỗi dãy x, ta thu được 1 xâu con của S: S[x[1]] S[x[2]] S[x[3]]… S[x[n]]

Để tạo ra được các xâu con phân biệt của S mà 2 phần tử liền kề khác nhau, ta chỉ xét đến những dãy x thỏa mãn điều kiện sau:

  1. S[x[i]] != S[x[i – 1]]
  2. Không tồn tại số k thỏa mãn x[i] < k < x[i + 1] và S[k] == S[x[i + 1]] (nói nôm na là nếu chọn ký tự ch nào đó để cho vào xâu con thì luôn chọn ký tự có chỉ số nhỏ nhất)

(cái đoạn in nghiêng này hình như không cần thiết :)))

 Gọi g[i][j] là số cách chọn dãy x[] có i phần tử mà x[i] = j.

 g[i][j] sẽ cập nhật cho g[i + 1][k] mà k là những giá trị mà khi thêm x[i + 1] = k thì vẫn đảm bảo điều kiện của dãy x[] ở trên (nhận xét là sẽ có không quá 26 giá trị của k)

g[i + 1][k] += g[i][j]

Cuối cùng, để tính kết quả bài toán:

Gọi:

  • f[i][j][0] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con bằng với xâu b[1..i]
  • f[i][j][1] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con lớn hơn xâu b

Với mỗi f[i][j][t], tìm các giá trị k thỏa mãn thêm x[i + 1] = k vẫn đảm bảo thỏa mãn điều kiện của x[]:

– Nếu t = 1 thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] = b[i + 1] thì f[i + 1][k][0] += f[i][j]

– Nếu t = 0, S[x[k]] > b[i + 1] thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] < b[i + 1] thì không làm gì hết

Kết quả bài toán = tổng f[i][j][1] + tổng f[length(b)][j][0]

Đpt ít hơn O(n * n * log(n)) n * n là mảng f, log(n) để tìm k, thực chất là không cần tính hết mảng f nên đpt sẽ nhỏ hơn khá nhiều

Solution ăn 100%:

QHĐ tương tự như trên, ta có thể tính được số xâu con của S[i..n] bắt đầu bằng ký tự ch bất kỳ mà thỏa mãn 2 ký tự liền kề khác nhau trong O(1)

Duyệt i từ đầu đến cuối xâu b, đến bước thứ i, đếm số xâu con trong S có dạng b[1..i – 1] + x với x là 1 xâu < S[i..m]. Số lượng xâu x = (số xâu con trong S[k..n] (k là vị trí kết thúc đầu tiên của xâu con b[1..i – 1] trong xâu S) bắt đầu bằng các ký tự < b[i]) + 1 (xâu rỗng)

Kết quả bài toán là tổng của các xâu trên – 1 (xâu rỗng)

Lưu ý là trong khi duyệt, nếu xâu b[1..i] không thỏa mãn điều kiện  2 ký tự liền kề khác nhau thì phải dừng duyệt ngay lập tức.

Solution O(N): của anh Nguyễn Tấn Sỹ Nguyên ( flash_mt )

Gọi F[i] là số cách chọn 1 subsequence ko có 2 phần tử kề nhau bằng nhau với S[i] là phần tử đầu tiên. Có thể tính F[] trong O(26N).

Sau đó ta đếm số lượng subsequence A thỏa A[1..k] = B[1..k] và A[k + 1] > B[k + 1]. Với mỗi giá trị k, xét A[k + 1] = c với c > B[k + 1], tìm vị trí u đầu tiên trong đoạn còn lại thỏa S[u] = c và tăng kết quả lên f[u]. Độ phức tạp của bước này là O(26(M + N)).

Code:

  • (đang cập nhập)

NKPANO – spoj

Đề bài:

Thuật toán:

  • Sắp xếp các công nhân tăng dần theo S
  • Gọi F[i] là tổng tiền công lớn nhất nếu sơn đến vạch i.
    Với mỗi công nhân thứ k: F[i]=max(F[i],F[j-1]+(i-j+1)*P[k]), trong đó: S[k]<=i<=S[k]+L[k]-1, i-L[k]+1<=j<=S[k]

Code:

#include 
#define maxn 16010
using namespace std;
int n,k,l;
int f[maxn+1],maxf[maxn+1],maxr[maxn+1];
struct  te{
    int l,p,s;
};
te a[102];
template  inline void read(T &x){
	x = 0; char c;
	while (!isdigit(c = getchar())) {}
	do x = x * 10 + c - '0'; while (isdigit(c = getchar()));
}
template  inline void write(T x){
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
void    docdl(){
    read(n); read(k);
    for(int i=1;i<=k;i++){
        read(a[i].l);
        read(a[i].p);
        read(a[i].s);
    }
}
bool    cmp(te a,te b){
    return (a.s<=b.s);
}
void    xuli(){
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++){
        maxr[a[i].s+1]=-1000000000;
        for(int j=a[i].s;j>=max(a[i].s-a[i].l+1,1);j--) maxr[j]=max(maxr[j+1],maxf[j-1]-(int)j*a[i].p);
        for(int j=a[i].s;j<=min(a[i].s+a[i].l-1,n);j++){
            f[j]=max(f[j],maxr[max(j-a[i].l+1,1)]+(int)(j+1)*a[i].p);
            maxf[j]=max(f[j],maxf[j-1]);
        }
        for(int j=1;j<=n;j++) maxf[j]=max(maxf[j],maxf[j-1]);
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    write(res);
}
int     main(){
    docdl();
    xuli();
}